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

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

  • a0=a1==ak2=0a_0=a_1=\cdots=a_{k-2}=0
  • ak1=1a_{k-1}=1
  • an=an1+an2++ank(nk)a_n=a_{n-1}+a_{n-2}+\cdots +a_{n-k}\:(n\geqq k)

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

フィボナッチ数列

k=2k=2 のとき,冒頭の式は a0=0,a1=1a_0=0,a_1=1 かつ an=an1+an2a_n=a_{n-1}+a_{n-2} となります。これはフィボナッチ数列です。

フィボナッチ数列の一般項は, an=15{(1+52)n(152)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\} と表わせます。ビネの公式と呼ばれます。→フィボナッチ数列の8つの性質(一般項・黄金比・互いに素)

x2=x+1x^2=x+1 の解を α=1+52,β=152\alpha=\dfrac{1+\sqrt{5}}{2},\beta=\dfrac{1-\sqrt{5}}{2} とおくと, an=αnαβ+βnβαa_n=\dfrac{\alpha^n}{\alpha-\beta}+\dfrac{\beta^n}{\beta-\alpha} とも書けます。

トリボナッチ数列

k=3k=3 のとき,a0=a1=0,a2=1a_0=a_1=0,a_2=1 かつ an=an1+an2+an3a_{n}=a_{n-1}+a_{n-2}+a_{n-3} で定まる数列です。これをトリボナッチ数列と呼びます。後ほど証明しますが,トリボナッチ数列の一般項は, an=αn(αβ)(αγ)+βn(βα)(βγ)+γn(γα)(γβ)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,\gammax3=x2+x+1x^3=x^2+x+1 の3つの解です。

k≧4のときの名前

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

一般項

定理

kk ナッチ数列の一般項は,

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

ただし,x1,...,xkx_1,...,x_kxk=xk1+xk2++x+1x^k=x^{k-1}+x^{k-2}+\cdots+x+1 の解。

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

証明
  1. まず,xkxk1xk2x1=0x^k-x^{k-1}-x^{k-2}-\cdots-x-1=0 の解がすべて異なることを示す。左辺を P(x)P(x) とおく。 P(x)(x1)=xk+12xk+1=Q(x)P(x)(x-1)=x^{k+1}-2x^k+1=Q(x) とおく。もし P(x)=0P(x)=0x=αx=\alpha で重解なら Q(x)=0Q(x)=0x=αx=\alpha で重解。つまり Q(α)=(k+1)αk2kαk1=0Q'(\alpha)=(k+1)\alpha^k-2k\alpha^{k-1}=0 α=0,2kk+1\alpha=0,\dfrac{2k}{k+1} が必要だが,いずれも P(α)0P(\alpha)\neq 0 である。

  2. よって,漸化式の特性方程式の意味とうまくいく理由 の定理より,定数 C1,...,CkC_1,...,C_k をうまく選べば an=i=1kCixina_n=\displaystyle\sum_{i=1}^kC_ix_i^n と表せる。

  3. あとは初期条件 a0,...,ak1a_0,...,a_{k-1} を確認すればよい。 (001)=(111x1x2xkx1k1x2k1xkk1)(C1C2Ck)\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} を満たす C1,...,CkC_1,...,C_k を求めたいが,右辺の行列はヴァンデルモンド行列であり逆行列が明示的に求まる。→ヴァンデルモンド行列とその逆行列
    計算すると Ci=1ji(xixj)C_i=\dfrac{1}{\prod_{j\neq i}(x_i-x_j)} となる。

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