トリボナッチ数列、テトラナッチ数列とその一般項

更新 2023/08/05

この記事では，フィボナッチ数列の一般化である，以下のような数列を考えます。以下 $k\geqq 2$ とします。

$a_0=a_1=\cdots=a_{k-2}=0$
$a_{k-1}=1$
$a_n=a_{n-1}+a_{n-2}+\cdots +a_{n-k}\:(n\geqq k)$

で定まる数列について考える。

フィボナッチ数列

k=2k=2k=2 のとき，冒頭の式は a0=0,a1=1a_0=0,a_1=1a0​=0,a1​=1 かつ
an=an−1+an−2a_n=a_{n-1}+a_{n-2}an​=an−1​+an−2​
となります。これはフィボナッチ数列です。
フィボナッチ数列の一般項は，
an=15{(1+52)n−(1−52)n}a_n=\dfrac{1}{\sqrt{5}}\left\{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right\}an​=5​1​{(21+5​​)n−(21−5​​)n}
と表わせます。ビネの公式と呼ばれます。→フィボナッチ数列の7つの性質（一般項・黄金比・互いに素）
x2=x+1x^2=x+1x2=x+1 の解を α=1+52,β=1−52\alpha=\dfrac{1+\sqrt{5}}{2},\beta=\dfrac{1-\sqrt{5}}{2}α=21+5​​,β=21−5​​ とおくと，
an=αnα−β+βnβ−αa_n=\dfrac{\alpha^n}{\alpha-\beta}+\dfrac{\beta^n}{\beta-\alpha}an​=α−βαn​+β−αβn​
とも書けます。

トリボナッチ数列

$k=3$ のとき， $a_0=a_1=0,a_2=1$ かつ $a_{n}=a_{n-1}+a_{n-2}+a_{n-3}$ で定まる数列です。これをトリボナッチ数列と呼びます。後ほど証明しますが，トリボナッチ数列の一般項は， $a_n=\dfrac{\alpha^n}{(\alpha-\beta)(\alpha-\gamma)}+\dfrac{\beta^n}{(\beta-\alpha)(\beta-\gamma)}+\dfrac{\gamma^n}{(\gamma-\alpha)(\gamma-\beta)}$ と書けます。ただし， $\alpha,\beta,\gamma$ は $x^3=x^2+x+1$ の3つの解です。

k≧4のときの名前

$k=4$ のときテトラナッチ数列と言います。
$k=5$ のときペンタナッチ数列と言います。
$k=6$ のときヘキサナッチ数列と言います。
$k=7$ のときヘプタナッチ数列と言います。
$k=8$ のときオクタナッチ数列と言います。
一般の $k$ に対しては k-ナッチ数列と言うことにします。→参考：Wikipedia

一般項

定理

$k$ ナッチ数列の一般項は，

$a_n=\displaystyle\sum_{i=1}^k\dfrac{x_i^n}{\prod_{j\neq i}(x_i-x_j)}$

ただし， $x_1,...,x_k$ は $x^k=x^{k-1}+x^{k-2}+\cdots+x+1$ の解。

$k=2$ とするとフィボナッチ数列の一般項になることを確認してみてください。

証明

まず， $x^k-x^{k-1}-x^{k-2}-\cdots-x-1=0$ の解がすべて異なることを示す。左辺を $P(x)$ とおく。 $P(x)(x-1)=x^{k+1}-2x^k+1=Q(x)$ とおく。もし $P(x)=0$ が $x=\alpha$ で重解なら $Q(x)=0$ も $x=\alpha$ で重解。つまり $Q'(\alpha)=(k+1)\alpha^k-2k\alpha^{k-1}=0$ $\alpha=0,\dfrac{2k}{k+1}$ が必要だが，いずれも $P(\alpha)\neq 0$ である。
よって，漸化式の特性方程式の意味とうまくいく理由の定理より，定数 $C_1,...,C_k$ をうまく選べば $a_n=\displaystyle\sum_{i=1}^kC_ix_i^n$ と表せる。
あとは初期条件 $a_0,...,a_{k-1}$ を確認すればよい。 $\begin{pmatrix}0\\0\\\vdots\\1\end{pmatrix}=\begin{pmatrix}1&1&\cdots&1\\x_1&x_2&\cdots&x_k\\\vdots&\vdots&\ddots&\vdots\\x_1^{k-1}&x_2^{k-1}&\cdots&x_k^{k-1}\end{pmatrix}\begin{pmatrix}C_1\\C_2\\\vdots\\C_k\end{pmatrix}$ を満たす $C_1,...,C_k$ を求めたいが，右辺の行列はヴァンデルモンド行列であり逆行列が明示的に求まる。→ヴァンデルモンド行列とその逆行列
計算すると $C_i=\dfrac{1}{\prod_{j\neq i}(x_i-x_j)}$ となる。

定理の証明の1はTwitterで教えていただきました、ありがとうございます！

この記事の監修者

マスオ

高校数学の美しい物語の管理人。「わかりやすいこと」と「ごまかさないこと」の両立を意識している。著書に『高校数学の美しい物語』『超ディープな算数の教科書』。記事の誤植やわかりにくい等のご指摘はお気軽にメールください！