文献あり

k-ナッチ数とk-リュカ数の行列表示と成分の双対関係

137

はじめに

putputlaw さんの Fibonacci trace formula の記事で、k-ナッチ数とk-リュカ数を行列のトレース(斜め方向の和)で表現する方法を教えていただきました。その行列表現を計算していて、双対というべき美しい関係を見つけたので、この記事ではその関係を紹介したいと思います。

マイナス項への拡張

今から紹介する行列式の表現には、 $k$ -ナッチ数・ $k$ -リュカ数のマイナス項がでてきますので、マイナス項を計算できるように定義域を拡張しておきます。
漸化式が成り立つようにマイナス項を定めると一意に定まり、次のようになります。

k

-ナッチ数・

k

-リュカ数のマイナス項

$2$ -ナッチ数(フィボナッチ数)と $2$ -リュカ数(リュカ数)
$\begin{array}{cc} n & - 2 & - 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \dots \\ F_{n}^{[2]} & - 1 & 1 & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & \dots \\ L_{n}^{[2]} & 3 & - 1 & 2 & 1 & 3 & 4 & 7 & 11 & 18 & 29 & 47 & 76 & 123 & \dots \end{array}$
$3$ -ナッチ数(トリボナッチ数)と $3$ -リュカ数
$\begin{array}{cc} n & - 3 & - 2 & - 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \dots \\ F_{n}^{[3]} & 0 & - 1 & 1 & 0 & 0 & 1 & 1 & 2 & 4 & 7 & 13 & 24 & 44 & \dots \\ L_{n}^{[3]} & 5 & - 1 & - 1 & 3 & 1 & 3 & 7 & 11 & 21 & 39 & 71 & 131 & 241 & \dots \end{array}$
$4$ -ナッチ数(テトラナッチ数)と $4$ -リュカ数
$\begin{array}{cc} n & - 4 & - 3 & - 2 & - 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \dots \\ F_{n}^{[4]} & 0 & 0 & - 1 & 1 & 0 & 0 & 0 & 1 & 1 & 2 & 4 & 8 & 15 & \dots \\ L_{n}^{[4]} & 7 & - 1 & - 1 & - 1 & 4 & 1 & 3 & 7 & 15 & 26 & 51 & 99 & 191 & \dots \end{array}$
$5$ -ナッチ数(ペンタナッチ数)と $5$ -リュカ数
$\begin{array}{cc} n & - 5 & - 4 & - 3 & - 2 & - 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & \dots \\ F_{n}^{[5]} & 0 & 0 & 0 & - 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 4 & \dots \\ L_{n}^{[5]} & 9 & - 1 & - 1 & - 1 & - 1 & 5 & 1 & 3 & 7 & 15 & 31 & 57 & 113 & \dots \end{array}$

k-ナッチ数とk-リュカ数の行列表示

次のような行列を考えます。

$M_{k} := (\begin{array}{cccc} 0 & \dots & 0 & 1 \\ 1 & ⋱ & ⋮ & ⋮ \\ ⋱ & 0 & ⋮ \\ 0 & 1 & 1 \end{array})$

転置行列はこんな感じになります。

$M_{k}^{T} = (\begin{array}{cccc} 0 & 1 & 0 \\ ⋮ & ⋱ & ⋱ \\ 0 & \dots & 0 & 1 \\ 1 & \dots & \dots & 1 \end{array})$

転置行列を使うと、 $k$ -ナッチ数・ $k$ -リュカ数の漸化式はこんな風に表現できます。

$(\begin{matrix} F_{n - k + 2}^{[k]} \\ F_{n - k + 3}^{[k]} \\ ⋮ \\ F_{n + 1}^{[k]} \end{matrix}) = \underset{M_{k}^{T} =}{\underset{⏟}{(\begin{array}{cccc} 0 & 1 & 0 \\ ⋮ & ⋱ & ⋱ \\ 0 & \dots & 0 & 1 \\ 1 & \dots & \dots & 1 \end{array})}} (\begin{matrix} F_{n - k + 1}^{[k]} \\ F_{n - k + 2}^{[k]} \\ ⋮ \\ F_{n}^{[k]} \end{matrix})$

$(\begin{matrix} L_{n - k + 2}^{[k]} \\ L_{n - k + 3}^{[k]} \\ ⋮ \\ L_{n + 1}^{[k]} \end{matrix}) = \underset{M_{k}^{T} =}{\underset{⏟}{(\begin{array}{cccc} 0 & 1 & 0 \\ ⋮ & ⋱ & ⋱ \\ 0 & \dots & 0 & 1 \\ 1 & \dots & \dots & 1 \end{array})}} (\begin{matrix} L_{n - k + 1}^{[k]} \\ L_{n - k + 2}^{[k]} \\ ⋮ \\ L_{n}^{[k]} \end{matrix})$

繰り返し $M_{k}^{T}$ を作用させて一般化するとこういうふうにもできます。

$(\begin{matrix} F_{n - k + m + 1}^{[k]} \\ F_{n - k + m + 2}^{[k]} \\ ⋮ \\ F_{n + m}^{[k]} \end{matrix}) = {(M_{k}^{T})}^{m} (\begin{matrix} F_{n - k + 1}^{[k]} \\ F_{n - k + 2}^{[k]} \\ ⋮ \\ F_{n}^{[k]} \end{matrix})$

$(\begin{matrix} L_{n - k + 2}^{[k]} \\ L_{n - k + 3}^{[k]} \\ ⋮ \\ L_{n + 1}^{[k]} \end{matrix}) = {(M_{k}^{T})}^{m} (\begin{matrix} L_{n - k + 1}^{[k]} \\ L_{n - k + 2}^{[k]} \\ ⋮ \\ L_{n}^{[k]} \end{matrix})$

この記事では行列のトレース(対角和)を
$tr (M)$
のように書きます。行列のトレースとは、正方行列の左上から右下方向の成分の和で、行列の固有値の和に一致するなど面白い性質があります。たとえば、 $M_{k}$ のトレースは
　　 $tr (M_{k}) = tr (M_{k}^{T}) = 1$
となります。
　また、行列の固有多項式を
$P_{k} (x)$
のように書きます。具体的には
$P_{k} (x) = x^{k} - x^{k - 1} - \dots - x - 1$
となり、k-ナッチ数の漸化式ととてもよく似た形になります。また、固有多項式の導関数を
$P_{k}^{'} (x)$
のように書きます。
$M_{k}$ の固有値を $α_{1}, α_{2}, \dots, α_{k}$ とします。これらの固有値が重複しないことは既知とします。

トレース、固有多項式及び固有値を使うと、次のような表現ができます。

　 $F_{n}^{[k]} = tr (M_{k}^{n} \cdot P^{'} (M_{k})^{- 1}) = \sum_{i = 1}^{k} \frac{α_{i}^{n}}{P^{'} (α_{i})}$

　 $L_{n}^{[k]} = tr (M_{k}^{n}) = \sum_{i = 1}^{k} α_{i}^{n}$

行列のトレースの表現と、固有値の表現がキレイに対応していますね!
さらに、具体的に $M_{k}^{n}$ や $P^{'} (M_{k})$ 計算してみると、行列の中に $k$ -ナッチ数・ $k$ -リュカ数がたくさんでてきます。

具体例

まずは計算結果を示しますので、法則性をさがしてみてください。

M_{k}^{n}

の具体例

$M_{2}^{2} = (\begin{array}{cc} 1 & 1 \\ 1 & 2 \end{array}), M_{2}^{3} = (\begin{array}{cc} 1 & 2 \\ 2 & 3 \end{array}), M_{2}^{4} = (\begin{array}{cc} 2 & 3 \\ 3 & 5 \end{array}),$

$M_{3}^{2} = (\begin{array}{ccc} 0 & 1 & 1 \\ 0 & 1 & 2 \\ 1 & 1 & 2 \end{array}), M_{3}^{3} = (\begin{array}{ccc} 1 & 1 & 2 \\ 1 & 2 & 3 \\ 1 & 2 & 4 \end{array}), M_{3}^{4} = (\begin{array}{ccc} 1 & 2 & 4 \\ 2 & 3 & 6 \\ 2 & 4 & 7 \end{array}),$

$M_{4}^{2} = (\begin{array}{cccc} 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 2 \\ 1 & 0 & 1 & 2 \\ 0 & 1 & 1 & 2 \end{array}), M_{4}^{3} = (\begin{array}{cccc} 0 & 1 & 1 & 2 \\ 0 & 1 & 2 & 3 \\ 0 & 1 & 2 & 4 \\ 1 & 1 & 2 & 4 \end{array}), M_{4}^{4} = (\begin{array}{cccc} 1 & 1 & 2 & 4 \\ 1 & 2 & 3 & 6 \\ 1 & 2 & 4 & 7 \\ 1 & 2 & 4 & 8 \end{array}) .$

P^{'} (M_{k})

の具体例

$P^{'} (M_{2}) = (\begin{array}{cc} - 1 & 2 \\ 2 & 1 \end{array}), P^{'} (M_{3}) = (\begin{array}{cccc} - 1 & 3 & 1 \\ - 2 & 2 & 4 \\ 3 & 1 & 3 \end{array}), P^{'} (M_{4}) = (\begin{array}{cccc} - 1 & 4 & 1 & 3 \\ - 2 & 3 & 5 & 4 \\ - 3 & 2 & 4 & 8 \\ 4 & 1 & 3 & 7 \end{array}) .$

法則性

それでは私が見つけた法則性を紹介します。

$M_{k}^{n}$ の $i j$ 成分を $a_{i j}$ と、 $P^{'} (M_{k})$ の $i j$ 成分を $b_{i j}$ とそれぞれ表すと、次のような法則性が観察できます。

M_{k}^{n}

や

P^{'} (M_{k})

の成分の法則性についての予想

$a_{i j} = \sum_{t = 0}^{i - 1} F_{n + j - t - 2}^{[k]}$

$b_{i j} = \sum_{t = 0}^{i - 1} L_{j - t - 2}^{[k]}$

この記事を投稿した当初は、私自身では証明していなかったので上記の式は「予想」だったのですが、投稿してすぐに子葉さんが重解のない固有方程式を持つ数列の行列表現とその成分の記事でこの予想が正しいことを一般化したうえで(!)証明していただきました。
ありがとうございます!
複雑そうな式がどんどん簡単になっていく様子が楽しいので、そちらの記事もぜひご覧ください!