k-ナッチ数とk-リュカ数

347

はじめに

この記事では、まず通常のフィボナッチ数とリュカ数の性質について紹介し、次に、それを一般化したものとして考えた $k$-ナッチ数と $k$-リュカ数の性質について紹介します。リュカ数というのは、フィボナッチ数と対で紹介されることが多く、フィボナッチ数と深い関係のある数で、私はフィボナッチ数とリュカ数はきょうだいのような関係だと思っています。

「リュカ数」と「リュカ数列」の違い

Wikipedia では「リュカ数」と「リュカ数列」は別の意味で定義されています。
「リュカ数(Lucas number)」は狭い概念で、フィボナッチ数の同伴数列である特定の数列にある項のこととされています。
一方、「リュカ数列(Lucas sequence)」は広い概念で、フィボナッチ数、リュカ数、ペル数, メルセンヌ数など数論に現れる重要な数列を含むものとされています。
この記事では、数列について書いていますが、「リュカ数列」と表現すると誤解を招く可能性があることから、数列の意味でも「フィボナッチ数」「リュカ数」という用語を使っています。
他に良い書き方があれば教えてください。

フィボナッチ数とリュカ数

漸化式による定義

フィボナッチ数の第 $n$ 項を $F_n$ と、リュカ数の第 $n$ 項を $L_n$ と書きます。($n\ge0$)
フィボナッチ数とリュカ数は次のように漸化式で定義することができます。

フィボナッチ数とリュカ数の漸化式

$$ \begin{eqnarray} \left\{ \begin{array}{l} F_n = 0&(n=0),\\ F_{n} = 1&(n=1),\\ F_{n+2} =F_{n}+F_{n+1}&(n \ge 0). \end{array} \right. \end{eqnarray}$$

$$ \begin{eqnarray} \left\{ \begin{array}{l} L_n =2&(n =0),\\ L_{n} = 1&(n=1),\\ L_{n+2} =L_{n}+L_{n+1}&(n \ge 0). \end{array} \right. \end{eqnarray}$$

フィボナッチ数とリュカ数は、初期値が異なるだけで漸化式は全く同じです。

母関数

母関数は次のようになります。

$f(x):=x^2-x-1$ と定義する。
また、$f(x)$ の導関数を $f{}'(x)$ で表す。

・　フィボナッチ数の母関数
${\displaystyle\frac{1}{xf(\frac{1}{x})}=F_0+F_1x+F_2x^2+F_3x^3+\cdots}$

・　リュカ数の母関数
${\displaystyle\frac{f{}'(\frac{1}{x})}{xf(\frac{1}{x})}=L_0+L_1x+L_2x^2+L_3x^3+\cdots}$

フィボナッチ数の母関数の分子に$f{}'(\frac{1}{x})$を乗せるとリュカ数の母関数になります。

一般項(ビネの公式)

フィボナッチ数とリュカ数の一般項

　　${\displaystyle F_n = \sum_{i=1}^{2} \frac{\alpha_i^{n}}{f{}'(\alpha_i)} }$

　　${\displaystyle L_n = \sum_{i=1}^{2} \alpha_i^{n} }$

ただし、$\alpha_1,\alpha_2$ は $f(x)=0$ の$2$個の解を表す。

後で一般化した式と対応させるために、$f'(x)$ を使って表現しています。
フィボナッチ数の一般項の分母の $f{}'(\alpha_i)$ を消すとリュカ数の一般項になります。

一般項(四捨五入による表現)

$k$-ナッチ数と $k$-リュカ数の一般項の四捨五入表現

$f(x)=0$ は正の実数解をただ１つ持つから、これを $\varphi$ とする。

　　${\displaystyle F_n=\left\lfloor \frac{\varphi^n}{f'(\varphi)} \right\rceil \qquad(n\ge0) }$

　　${\displaystyle L_n=\left\lfloor \varphi^n \right\rceil \qquad(n\ge2) }$

参考: フィボナッチ数の一般項の四捨五入による表現の導出

行列による表現

$ \left( \begin{array}{c} F_{n} \\ F_{n+1} \end{array} \right) = \underbrace{ \left( \begin{array}{cc} 0& 1\\ 1 & 1 \end{array} \right)}_{M_2^{\mathrm{T}}:=} \left( \begin{array}{c} F_{n-1}\\ F_{n} \end{array} \right) $

$M_2$ の固有方程式は $f(x)$ ですから、ケイリー・ハミルトンの定理より $M_2^2=M_2+I$ の漸化式が成り立ちます。さらに、$\alpha_1,\alpha_2$ は $M_2$ の固有値です。そして、リュカ数は次のように表すことができます。

$L_n=\mathrm{trace}\left(M_2^n\right)=\alpha_1^n+\alpha_2^n$

参考: Wikipedia 行列の「転置」「トレース」

この記事では $M^{\mathrm{T}}$ で転置を、$\mathrm{trace}(M)$ でトレースを表しています。

$k$-ナッチ数と $k$-リュカ数

具体例

それではここから、私が $k$-リュカ数にふさわしいと考える数列を紹介していきます。

$k$-ナッチ数と $k$-リュカ数

$2$-ナッチ数(フィボナッチ数)と $2$-リュカ数(リュカ数)
${\displaystyle \begin{array}{|c|*5{c|}}\hline n&0&1&2&3&4&5&6&7&8&9&10&11&12&\cdots\\ \hline F_n^{[2]}&0&1&1&2&3&5&8&13&21&34&55&89&144&\cdots\\ \hline L_n^{[2]}&2&1&3&4&7&11&18&29&47&76&123&199&322&\cdots\\ \hline \end{array} }$
$3$-ナッチ数(トリボナッチ数)と $3$-リュカ数
${\displaystyle \begin{array}{|c|*5{c|}}\hline n&0&1&2&3&4&5&6&7&8&9&10&11&12&\cdots\\ \hline F_n^{[3]}&0&0&1&1&2&4&7&13&24&44&81&149&274&\cdots\\ \hline L_n^{[3]}&3&1&3&7&11&21&39&71&131&241&443&815&1499&\cdots\\ \hline \end{array} }$
$4$-ナッチ数(テトラナッチ数)と $4$-リュカ数
${\displaystyle \begin{array}{|c|*5{c|}}\hline n&0&1&2&3&4&5&6&7&8&9&10&11&12&\cdots\\ \hline F_n^{[4]}&0&0&0&1&1&2&4&8&15&29&56&108&208&\cdots\\ \hline L_n^{[4]}&4&1&3&7&15&26&51&99&191&367&708&1365&2631&\cdots\\ \hline \end{array} }$
$5$-ナッチ数(ペンタナッチ数)と $5$-リュカ数
${\displaystyle \begin{array}{|c|*5{c|}}\hline n&0&1&2&3&4&5&6&7&8&9&10&11&12&\cdots\\ \hline F_n^{[5]}&0&0&0&0&1&1&2&4&8&16&31&61&120&\cdots\\ \hline L_n^{[5]}&5&1&3&7&15&31&57&113&223&439&863&1695&3333&\cdots\\ \hline \end{array} }$

……具体例だけだとよくわからないですよね。
この数列がなぜリュカ数の一般化といえるのか説明します。

漸化式による定義

$k$-ナッチ数の第 $n$ 項を $F^{[k]}_n$ と、 $k$-リュカ数の第 $n$ 項を $L^{[k]}_n$ と書きます。($n\ge0$)
$k$-ナッチ数と $k$-リュカ数は次のように漸化式で定義することができます。

$k$-ナッチ数と $k$-リュカ数の漸化式

$$ \begin{eqnarray} \left\{ \begin{array}{l} F^{[k]}_n = 0&(0\le n\le k-2),\\ F^{[k]}_{n} = 1&(n=k-1),\\ F^{[k]}_{n+k} =F^{[k]}_{n}+F^{[k]}_{n+1}+F^{[k]}_{n+2}+\cdots+F^{[k]}_{n+k-1} &(n \ge 0). \end{array} \right. \end{eqnarray}$$

$$ \begin{eqnarray} \left\{ \begin{array}{l} L^{[k]}_n =k&(n =0),\\ L^{[k]}_{n} = 2^n-1&(1\le n \le k-1),\\ L^{[k]}_{n+k} =L^{[k]}_{n}+L^{[k]}_{n+1}+L^{[k]}_{n+2}+\cdots+L^{[k]}_{n+k-1} &(n \ge 0). \end{array} \right. \end{eqnarray}$$

$k$-ナッチ数と $k$-リュカ数は、初期値が異なるだけで漸化式は全く同じです。
$k=2$ のときは、フィボナッチ数・リュカ数の漸化式による定義と一致します。

母関数

母関数は次のようになります。

$f^{[k]}(x):=x^k-x^{k-1}-\cdots-x^2-x-1$ と定義する。
また、$f^{[k]}(x)$ の導関数を $f^{[k]}{}'(x)$ で表す。

・　$k$-ナッチ数の母関数
${\displaystyle\frac{1}{xf^{[k]}(\frac{1}{x})}=F^{[k]}_0+F^{[k]}_1x+F^{[k]}_2x^2+F^{[k]}_3x^3+\cdots}$

・　$k$-リュカ数の母関数
${\displaystyle\frac{f^{[k]}{}'(\frac{1}{x})}{xf^{[k]}(\frac{1}{x})}=L^{[k]}_0+L^{[k]}_1x+L^{[k]}_2x^2+L^{[k]}_3x^3+\cdots}$

$k$-ナッチ数の母関数の分子に$f^{[k]}{}'(\frac{1}{x})$を乗せると$k$-リュカ数の母関数になります。
$k=2$ のときは、フィボナッチ数・リュカ数の母関数と一致します。

一般項(ビネの公式に類似した表現)

$k$-ナッチ数と $k$-リュカ数の一般項

　　${\displaystyle F^{[k]}_n = \sum_{i=1}^{k} \frac{\alpha_i^{n}}{f^{[k]}{}'(\alpha_i)} }$

　　${\displaystyle L^{[k]}_n = \sum_{i=1}^{k} \alpha_i^{n} }$

ただし、$\alpha_1,\alpha_2,\cdots,\alpha_k$ は $f(x)=0$ の$k$個の解を表す。

$k$-ナッチ数の一般項の分母の $f^{[k]}{}'(\alpha_i)$ を消すと$k$-リュカ数の一般項になります。
この $k$-リュカ数の一般項が漸化式を満たすことは $\alpha_i^k=\alpha_i+\alpha_i^2+\cdots+\alpha_i^{k-1}$ であることからわかります。また、初期値が条件を満たすことは、こちらの記事を見てください。
参考: x^k-x^(k-1)-…x-1=0 の解の累乗の和についての予想(その2・予想の証明とk-リュカ数)

一般項(四捨五入による表現)

$k$-ナッチ数と $k$-リュカ数の一般項の四捨五入表現

$f^{[k]}(x)=0$ は正の実数解をただ１つ持つから、これを $\varphi^{[k]}$ とする。

　　${\displaystyle F^{[k]}_n=\left\lfloor \frac{\left(\varphi^{[k]}\right)^n}{f^{[k]}{}'(A_k)} \right\rceil \qquad(n\ge0) }$

　　${\displaystyle L^{[k]}_n\fallingdotseq\left\lfloor \left(\varphi^{[k]}\right)^n \right\rceil \qquad\text{(nが大きいときは等号となる)} }$

この四捨五入表現、$k$-ナッチ数についてはすべての非負整数 $n$ に対して成立するのですが、$k$-リュカ数については残念ながらすべての非負整数 $n$ について成立するわけではなく、$n$ が小さいときは誤差の絶対値が $\frac{1}{2}$ を超えてしまい、ズレることがあります。とはいえ、$n$ が大きいときは誤差の絶対値が $\frac{1}{2}$ 未満となり、等号にできるはずです。
どのくらい大きければ等号にできるかの境界についてはまだ調べていません。

参考: フィボナッチ数列を拡張したk-ナッチ数列の一般項についての予想(その4・証明完成)

行列による表現

これは putputlaw さんに　 A Combinatorial Interpretation of @apu_yokai's k-Lucas Number Identity の記事で教えていただいた方法です。

$ \left( \begin{array}{c} F^{[k]}_{n-k+2} \\ F^{[k]}_{n-k+3} \\ \vdots \\ F^{[k]}_{n+1} \end{array} \right) = \underbrace{ \left( \begin{array}{cccc} 0& 1& & 0\\ \vdots & \ddots& \ddots & \\ 0 & \cdots & 0 &1 \\ 1 & \cdots& \cdots & 1 \end{array} \right)}_{M_k^{\mathrm{T}}:=} \left( \begin{array}{c} F^{[k]}_{n-k+1}\\ F^{[k]}_{n-k+2} \\ \vdots \\ F^{[k]}_{n} \end{array} \right) $

$M_k$ の固有方程式は $f(x)$ ですから、ケイリー・ハミルトンの定理より $M_k^k=M_k^{k-1}+\cdots+M+I$ の漸化式が成り立ちます。さらに、$\alpha_1,\alpha_2,\cdots,\alpha_k$ は $M_k$ の固有値です。そして、$k$-リュカ数は次のように表すことができます。

$L^{[k]}_n=\mathrm{trace}\left(M_k^n\right)=\alpha_1^n+\ldots+\alpha_k^n$

この形の行列はフロベニウスの同伴行列といい、固有方程式が簡単にわかります。
参考: Wikipedia 同伴行列

※ この部分は putputlaw さんに教えていただきました。