この記事では$k$-ナッチ数を$k$-リュカ数の和として表す公式を導出します。
いま$f(x)=x^k-\sum^{k-1}_{j=0}x^j$とおき、その根をそれぞれ$\a_1,\a_2,\ldots,\a_k$とすると$k$-ナッチ数$F_n^{(k)}$、$k$-リュカ数$L_n^{[k]}$はそれぞれ
$\dis F_n^{[k]}=\sum^k_{j=1}\frac{\a_j^n}{f'(\a_j)},\quad L_n^{[k]}=\sum^k_{j=1}\a_j^n$
と表せれるのでした。よって$k$-リュカ数は$k$-ナッチ数によって
\begin{eqnarray}
L_n^{[k]}&=&\sum^k_{i=1}f'(\a_i)\frac{\a_i^n}{f'(\a_i)}
=\sum^k_{i=1}(k\a_i^{k-1}-\sum^{k-1}_{j=0}j\a_i^{j-1})\frac{\a_i^n}{f'(\a_i)}
\\&=&k\sum^k_{i=1}\frac{\a_i^{n+k-1}}{f'(\a_i)}-\sum^{k-1}_{j=1}j(\sum^k_{i=1}\frac{\a_i^{n+j-1}}{f'(\a_i)})
\\&=&kF_{n+k-1}^{[k]}-\sum^{k-1}_{j=1}jF_{n+j-1}^{[k]}
=\sum^{k-1}_{j=1}(k-j)F_{n+j-1}^{[k]}+kF_{n-1}^{[k]}
\end{eqnarray}
のように表すことができます。では逆に$k$-ナッチ数を$k$-リュカ数で表現しようとするとどうなるのでしょうか。それを考えてみたところ以下のような式が得られました。
$\dis F_n^{[k]}=\frac{k-1}{2(2k)^k-(k+1)^{k+1}}\left(\sum^{k-1}_{j=1}(k+1)^{k-1-j}((k+1)^j-2(2k)^{j-1})L_{n-j+1}^{[k]}+\frac{2((2k)^{k-1}-(k+1)^{k-1})}{k-1}L_{n-k+1}^{[k]}\right)$
かなりごちゃごちゃしていますが、具体的に$k=2,3,4,5,6$のときを計算してみると
\begin{eqnarray}
F_n^{[2]}&=&\frac{L_n^{[2]}+2L_{n-1}^{[2]}}{5}=\frac{L_{n+1}^{[2]}+L_{n-1}^{[2]}}{5}
\\F_n^{[3]}&=&\frac{1}{88}(8L_n^{[3]}+4L_{n-1}^{[3]}+20L_{n-2}^{[3]})
\\&=&\frac{2L_n^{[3]}+L_{n-1}^{[3]}+5L_{n-2}^{[3]}}{22}
\\F_n^{[4]}&=&\frac{1}{1689}(75L_{n}^{[4]}+45L_{n-1}^{[4]}-3L_{n-2}^{[4]}+258L_{n-3}^{[4]})
\\&=&\frac{25L_{n}^{[4]}+15L_{n-1}^{[4]}-L_{n-2}^{[4]}+86L_{n-3}^{[4]}}{563}
\\F_n^{[5]}&=&\frac{1}{38336}(864L_{n}^{[5]}+576L_{n-1}^{[5]}+96L_{n-2}^{[5]}-704L_{n-3}^{[5]}+4352L_{n-4}^{[5]})
\\&=&\frac{27L_{n}^{[5]}+18L_{n-1}^{[5]}+3L_{n-2}^{[5]}-22L_{n-3}^{[5]}+136L_{n-4}^{[5]}}{1198}
\\F_n^{[6]}&=&\frac{1}{1029685}(12005L_{n}^{[6]}+8575L_{n-1}^{[6]}+2695L_{n-2}^{[6]}-7385L_{n-3}^{[6]}-24665L_{n-4}^{[6]}+92810L_{n-5}^{[6]})
\\&=&\frac{2401L_{n}^{[6]}+1715L_{n-1}^{[6]}+539L_{n-2}^{[6]}-1477L_{n-3}^{[6]}-4933L_{n-4}^{[6]}+18562L_{n-5}^{[6]}}{205937}
\end{eqnarray}
となります。$k=6$のときの分母に現れる$205937$は素数なこともあって、とても実用的とは言えなさそうですね。
上で$k$-リュカ数を$k$-ナッチ数で表したときを思い出すと、$\a=\a_1,\a_2,\ldots,\a_k$に対し$\dis\frac{1}{f'(\a)}$を負の冪を許した$\a$についての多項式で表せれればよいことになります。つまりは以下の等式を示します。
$\dis\frac{1}{f'(\a)}=\frac{k-1}{2(2k)^k-(k+1)^{k+1}}\left(\sum^{k-1}_{j=1}(k+1)^{k-1-j}((k+1)^j-2(2k)^{j-1})\a^{-j+1}+\frac{2((2k)^{k-1}-(k+1)^{k-1})}{k-1}\a^{-k+1}\right)$
まず$(x-1)f(x)=x^{k+1}-2x^k+1$から$(\a-1)f'(\a)=\a^{k-1}((k+1)\a-2k)$つまり
$\dis \frac1{f'(\a)}=\frac{1}{\a^{k-1}}\cdot\frac{\a-1}{(k+1)\a-2k}$
を得ます。そして$\frac{1}{(k+1)\a-2k}$の有理化を考えると
\begin{eqnarray}
\frac{1}{(k+1)\a-2k}&=&-\frac1{\prod^k_{j=1}(2k-(k+1)\a_j)}\cdot\frac{\prod^k_{j=1}(2k-(k+1)\a_j)}{2k-(k+1)\a}
\\&=&-\frac{1}{(k+1)^kf(\frac{2k}{k+1})}\cdot\frac{(k+1)^{k-1}f(\frac{2k}{k+1})}{\frac{2k}{k+1}-\a}
\end{eqnarray}
となるのでそれぞれの因子を具体的に計算してみましょう。
$\dis(k+1)^kf(\frac{2k}{k+1})=\frac{(k+1)^{k+1}-2(2k)^k}{k-1}$が成り立つ。
$(x-1)f(x)=x^{k+1}-2x^k+1$から
\begin{eqnarray}
(k+1)^kf(\frac{2k}{k+1})&=&(k+1)^k\frac{(\frac{2k}{k+1})^{k+1}-2(\frac{2k}{k+1})^k+1}{\frac{2k}{k+1}-1}
\\&=&\frac{(2k)^{k+1}-2(k+1)(2k)^k+(k+1)^{k+1}}{2k-(k+1)}
\\&=&\frac{(2k)^{k+1}-2k(2k)^k-2(2k)^k+(k+1)^{k+1}}{k-1}
\\&=&\frac{(k+1)^{k+1}-2(2k)^k}{k-1}
\end{eqnarray}
とわかる。
$\dis\frac{(k+1)^{k-1}f(\frac{2k}{k+1})}{\frac{2k}{k+1}-\a} =\frac{1}{\a-1}\left(\sum^{k-1}_{j=1}(k+1)^{j-1}((k+1)^{k-j}-2(2k)^{k-1-j})\a^{j}+\frac{2((2k)^{k-1}-(k+1)^{k-1})}{k-1}\right)$が成り立つ。
これは以下の補題から直ちに得られます。
$\dis \frac{f(x)}{x-\a}=\frac1{\a-1}\left(\sum^{k-1}_{j=1}(x^{k-j}-2x^{k-j-1}+1)\a^j+(1-\frac{x^k-2x^{k-1}+1}{x-1})\right)$が成り立つ。
$\dis\frac{f(x)}{x-\a}=\sum^{k-1}_{j=0}c_jx^j$とおくと$\dis f(x)=(x-\a)\frac{f(x)}{x-\a}=x^k-\sum^{k-1}_{j=0}x^j$より
$c_{k-1}=1,c_{j-1}-\a c_j=-1$なので$c_j$は
$\dis c_j=\a^{k-j-1}-\sum^{k-j-2}_{i=0}\a^i=\frac{\a^{k-j}-2\a^{k-j-1}+1}{\a-1}$
と求められる。よって
\begin{eqnarray}
(\a-1)\frac{f(x)}{x-\a}&=&\sum^{k-1}_{j=0}(\a^{j+1}-2\a^j+1)x^{k-j-1}
\\&=&(\a^k+\sum^{k-1}_{j=1}\a^jx^{k-j})-2(\sum^{k-1}_{j=1}\a^jx^{k-j-1}+x^{k-1})+\sum^{k-1}_{j=0}x^{k-j-1}
\\&=&\sum^{k-1}_{j=1}\a^j+\sum^{k-1}_{j=1}(x^{k-j}-2x^{k-j-1})\a^j-2x^{k-1}+\frac{x^k-1}{x-1}
\\&=&\sum^{k-1}_{j=1}(x^{k-j}-2x^{k-j-1}+1)\a^j+1-\frac{x^k-2x^{k-1}+1}{x-1}
\end{eqnarray}
を得る。
以上より補題2,3および
$\dis\frac{1}{f'(\a)}=\frac{1}{\a^{k-1}}\cdot\frac{1}{-(k+1)^kf(\frac{2k}{k+1})}\cdot\frac{(k+1)^{k-1}(\a-1)f(\frac{2k}{k+1})}{\frac{2k}{k+1}-\a}$
から命題1を得、冒頭で$k$-リュカ数の$k$-ナッチ数による表現を導出したのと同様にして公式1を得る。
ちなみに$\a^k(\a-2)+1=0$から
$\dis\frac{1}{f'(\a)}=\frac{\a(2-\a)}{-(k+1)^kf(\frac{2k}{k+1})}\cdot\frac{(k+1)^{k-1}(\a-1)f(\frac{2k}{k+1})}{\frac{2k}{k+1}-\a}$
とも表現できるので$k$-ナッチ数を$k$-リュカ数の$n$以降の項の線形結合で表すこともできるが補題3を見てわかるようにとても煩雑になるのであまりお勧めはしない。