k-ナッチ数とk-リュカ数の行列表示と成分の双対関係
はじめに
putputlaw さんの Fibonacci trace formula の記事で、k-ナッチ数とk-リュカ数を行列のトレース(斜め方向の和)で表現する方法を教えていただきました。その行列表現を計算していて、双対というべき美しい関係を見つけたので、この記事ではその関係を紹介したいと思います。
マイナス項への拡張
今から紹介する行列式の表現には、$k$-ナッチ数・$k$-リュカ数のマイナス項がでてきますので、マイナス項を計算できるように定義域を拡張しておきます。
漸化式が成り立つようにマイナス項を定めると一意に定まり、次のようになります。
$2$-ナッチ数(フィボナッチ数)と $2$-リュカ数(リュカ数)
${\displaystyle
\begin{array}{|c|*5{c|}}\hline
n&-2&-1&0&1&2&3&4&5&6&7&8&9&10&\cdots\\ \hline
F_n^{[2]}&-1&1&0&1&1&2&3&5&8&13&21&34&55&\cdots\\ \hline
L_n^{[2]}&3&-1&2&1&3&4&7&11&18&29&47&76&123&\cdots\\ \hline
\end{array}
}$
$3$-ナッチ数(トリボナッチ数)と $3$-リュカ数
${\displaystyle
\begin{array}{|c|*5{c|}}\hline
n&-3&-2&-1&0&1&2&3&4&5&6&7&8&9&\cdots\\ \hline
F_n^{[3]}&0&-1&1&0&0&1&1&2&4&7&13&24&44&\cdots\\ \hline
L_n^{[3]}&5&-1&-1&3&1&3&7&11&21&39&71&131&241&\cdots\\ \hline
\end{array}
}$
$4$-ナッチ数(テトラナッチ数)と $4$-リュカ数
${\displaystyle
\begin{array}{|c|*5{c|}}\hline
n&-4&-3&-2&-1&0&1&2&3&4&5&6&7&8&\cdots\\ \hline
F_n^{[4]}&0&0&-1&1&0&0&0&1&1&2&4&8&15&\cdots\\ \hline
L_n^{[4]}&7&-1&-1&-1&4&1&3&7&15&26&51&99&191&\cdots\\ \hline
\end{array}
}$
$5$-ナッチ数(ペンタナッチ数)と $5$-リュカ数
${\displaystyle
\begin{array}{|c|*5{c|}}\hline
n&-5&-4&-3&-2&-1&0&1&2&3&4&5&6&7&\cdots\\ \hline
F_n^{[5]}&0&0&0&-1&1&0&0&0&0&1&1&2&4&\cdots\\ \hline
L_n^{[5]}&9&-1&-1&-1&-1&5&1&3&7&15&31&57&113&\cdots\\ \hline
\end{array}
}$
k-ナッチ数とk-リュカ数の行列表示
次のような行列を考えます。
$ M_k:= \left( \begin{array}{cccc} 0 & \cdots&0 & 1\\ 1 & \ddots& \vdots &\vdots \\ & \ddots & 0 &\vdots \\ 0 & & 1 & 1 \end{array} \right) $
転置行列はこんな感じになります。
$ M_k^{\mathrm{T}}= \left( \begin{array}{cccc} 0& 1& & 0\\ \vdots & \ddots& \ddots & \\ 0 & \cdots & 0 &1 \\ 1 & \cdots& \cdots & 1 \end{array} \right) $
転置行列を使うと、$k$-ナッチ数・$k$-リュカ数の漸化式はこんな風に表現できます。
$ \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) $
$ \left( \begin{array}{c} L^{[k]}_{n-k+2} \\ L^{[k]}_{n-k+3} \\ \vdots \\ L^{[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} L^{[k]}_{n-k+1}\\ L^{[k]}_{n-k+2} \\ \vdots \\ L^{[k]}_{n} \end{array} \right) $
繰り返し $M_k^{\mathrm{T}}$ を作用させて一般化するとこういうふうにもできます。
$ \left( \begin{array}{c} F^{[k]}_{n-k+m+1} \\ F^{[k]}_{n-k+m+2} \\ \vdots \\ F^{[k]}_{n+m} \end{array} \right) = {\left(M_k^{\mathrm{T}}\right)^m} \left( \begin{array}{c} F^{[k]}_{n-k+1}\\ F^{[k]}_{n-k+2} \\ \vdots \\ F^{[k]}_{n} \end{array} \right) $
$ \left( \begin{array}{c} L^{[k]}_{n-k+2} \\ L^{[k]}_{n-k+3} \\ \vdots \\ L^{[k]}_{n+1} \end{array} \right) = {\left(M_k^{\mathrm{T}}\right)^m} \left( \begin{array}{c} L^{[k]}_{n-k+1}\\ L^{[k]}_{n-k+2} \\ \vdots \\ L^{[k]}_{n} \end{array} \right) $
この記事では行列のトレース(対角和)を
$\mathrm{tr}(M)$
のように書きます。行列のトレースとは、正方行列の左上から右下方向の成分の和で、行列の固有値の和に一致するなど面白い性質があります。たとえば、 $M_k$ のトレースは
$\mathrm{tr}(M_k)=\mathrm{tr}(M_k^{\mathrm{T}})=1$
となります。
また、行列の固有多項式を
$P_k(x)$
のように書きます。具体的には
$P_k(x)=x^k-x^{k-1}-\cdots-x-1$
となり、k-ナッチ数の漸化式ととてもよく似た形になります。また、固有多項式の導関数を
$P_k'(x)$
のように書きます。
$M_k$ の固有値を $\alpha_1,\alpha_2,\cdots,\alpha_k$ とします。これらの固有値が重複しないことは既知とします。
トレース、固有多項式及び固有値を使うと、次のような表現ができます。
${\displaystyle F^{[k]}_n=\mathrm{tr}\left(M_k^n\cdot P'(M_k)^{-1}\right)=\sum_{i=1}^{k}\frac{\alpha_i^n}{P'(\alpha_i)}}$
${\displaystyle L^{[k]}_n=\mathrm{tr}\left(M_k^n\right)=\sum_{i=1}^{k}\alpha_i^n}$
行列のトレースの表現と、固有値の表現がキレイに対応していますね!
さらに、具体的に $M_k^n$ や $P'(M_k)$ 計算してみると、行列の中に$k$-ナッチ数・$k$-リュカ数がたくさんでてきます。
具体例
まずは計算結果を示しますので、法則性をさがしてみてください。
$M_2^2= \left( \begin{array}{cc} 1& 1\\ 1& 2\\ \end{array} \right), M_2^3= \left( \begin{array}{cc} 1& 2\\ 2& 3\\ \end{array} \right), M_2^4= \left( \begin{array}{cc} 2& 3\\ 3& 5\\ \end{array} \right), $
$M_3^2= \left( \begin{array}{ccc} 0& 1& 1\\ 0& 1& 2\\ 1& 1& 2\\ \end{array} \right), M_3^3= \left( \begin{array}{ccc} 1& 1& 2\\ 1& 2& 3\\ 1& 2& 4\\ \end{array} \right), M_3^4= \left( \begin{array}{ccc} 1& 2& 4\\ 2& 3& 6\\ 2& 4& 7\\ \end{array} \right), $
$M_4^2= \left( \begin{array}{cccc} 0& 0& 1& 1\\ 0& 0& 1& 2\\ 1& 0& 1& 2\\ 0& 1& 1& 2\\ \end{array} \right), M_4^3= \left( \begin{array}{cccc} 0& 1& 1& 2\\ 0& 1& 2& 3\\ 0& 1& 2& 4\\ 1& 1& 2& 4\\ \end{array} \right), M_4^4= \left( \begin{array}{cccc} 1& 1& 2& 4\\ 1& 2& 3& 6\\ 1& 2& 4& 7\\ 1& 2& 4& 8\\ \end{array} \right). $
$P'(M_2)= \left( \begin{array}{cc} -1& 2\\ 2& 1\\ \end{array} \right), P'(M_3)= \left( \begin{array}{cccc} -1& 3& 1\\ -2& 2& 4\\ 3& 1& 3\\ \end{array} \right), P'(M_4)= \left( \begin{array}{cccc} -1& 4& 1& 3\\ -2& 3& 5& 4\\ -3& 2& 4& 8\\ 4& 1& 3& 7\\ \end{array} \right). $
法則性
それでは私が見つけた法則性を紹介します。
$M_k^n$ の $ij$ 成分を $a_{ij}$ と、$P'(M_k)$ の $ij$ 成分を $b_{ij}$ とそれぞれ表すと、次のような法則性が観察できます。
${\displaystyle a_{ij}= \sum_{t=0}^{i-1} F_{n+j-t-2}^{[k]} }$
${\displaystyle b_{ij}= \sum_{t=0}^{i-1} L_{j-t-2}^{[k]} }$
この記事を投稿した当初は、私自身では証明していなかったので上記の式は「予想」だったのですが、投稿してすぐに
子葉
さんが
重解のない固有方程式を持つ数列の行列表現とその成分
の記事でこの予想が正しいことを一般化したうえで(!)証明していただきました。
ありがとうございます!
複雑そうな式がどんどん簡単になっていく様子が楽しいので、そちらの記事もぜひご覧ください!
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
