文献あり

k-ナッチ数のk-リュカ数による表現

はじめに

　この記事では $k$ -ナッチ数を $k$ -リュカ数の和として表す公式を導出します。
　いま多項式
$f (x) = x^{k} - \sum_{j = 0}^{k - 1} x^{j}$
に対し、その根をそれぞれ $α_{1}, α_{2}, \dots, α_{k}$ とすると $k$ -ナッチ数 $F_{n}^{(k)}$ 、 $k$ -リュカ数 $L_{n}^{[k]}$ はそれぞれ
$F_{n}^{[k]} = \sum_{j = 1}^{k} \frac{α_{j}^{n}}{f^{'} (α_{j})}, L_{n}^{[k]} = \sum_{j = 1}^{k} α_{j}^{n}$
と表せるのでした。
　よって $k$ -リュカ数は $k$ -ナッチ数を用いて次のように表せることが直ちにわかります。

$L_{n}^{[k]} = \sum_{j = 1}^{k - 1} (k - j) F_{n + j - 1}^{[k]} + k F_{n - 1}^{[k]}$

$\begin{aligned} L_{n}^{[k]} & = \sum_{i = 1}^{k} f^{'} (α_{i}) \frac{α_{i}^{n}}{f^{'} (α_{i})} \\ = \sum_{i = 1}^{k} (k α_{i}^{k - 1} - \sum_{j = 0}^{k - 1} j α_{i}^{j - 1}) \frac{α_{i}^{n}}{f^{'} (α_{i})} \\ = k \sum_{i = 1}^{k} \frac{α_{i}^{n + k - 1}}{f^{'} (α_{i})} - \sum_{j = 1}^{k - 1} j \sum_{i = 1}^{k} \frac{α_{i}^{n + j - 1}}{f^{'} (α_{i})} \\ = k F_{n + k - 1}^{[k]} - \sum_{j = 1}^{k - 1} j F_{n + j - 1}^{[k]} \\ = \sum_{j = 1}^{k - 1} (k - j) F_{n + j - 1}^{[k]} + k F_{n - 1}^{[k]} \end{aligned}$
とわかる。

　では逆に $k$ -ナッチ数を $k$ -リュカ数で表現しようとするとどうなるのでしょうか。それを考えてみたところ以下のような式が得られました。

$F_{n}^{[k]} = \frac{k - 1}{2 (2 k)^{k} - (k + 1)^{k + 1}} (\sum_{j = 1}^{k - 1} (k + 1)^{k - 1 - j} ((k + 1)^{j} - 2 (2 k)^{j - 1}) L_{n - j + 1}^{[k]} + \frac{2 ((2 k)^{k - 1} - (k + 1)^{k - 1})}{k - 1} L_{n - k + 1}^{[k]})$

　かなりごちゃごちゃしていますが、具体的に $k = 2, 3, 4, 5, 6$ のときを計算してみると
$\begin{array}{rcl} F_{n}^{[2]} & = & \frac{L_{n}^{[2]} + 2 L_{n - 1}^{[2]}}{5} (= \frac{L_{n + 1}^{[2]} + L_{n - 1}^{[2]}}{5}) \\ F_{n}^{[3]} & = & \frac{1}{88} (8 L_{n}^{[3]} + 4 L_{n - 1}^{[3]} + 20 L_{n - 2}^{[3]}) \\ = & \frac{2 L_{n}^{[3]} + L_{n - 1}^{[3]} + 5 L_{n - 2}^{[3]}}{22} \\ F_{n}^{[4]} & = & \frac{1}{1689} (75 L_{n}^{[4]} + 45 L_{n - 1}^{[4]} - 3 L_{n - 2}^{[4]} + 258 L_{n - 3}^{[4]}) \\ = & \frac{25 L_{n}^{[4]} + 15 L_{n - 1}^{[4]} - L_{n - 2}^{[4]} + 86 L_{n - 3}^{[4]}}{563} \\ F_{n}^{[5]} & = & \frac{1}{38336} (864 L_{n}^{[5]} + 576 L_{n - 1}^{[5]} + 96 L_{n - 2}^{[5]} - 704 L_{n - 3}^{[5]} + 4352 L_{n - 4}^{[5]}) \\ = & \frac{27 L_{n}^{[5]} + 18 L_{n - 1}^{[5]} + 3 L_{n - 2}^{[5]} - 22 L_{n - 3}^{[5]} + 136 L_{n - 4}^{[5]}}{1198} \\ F_{n}^{[6]} & = & \frac{1}{1029685} (12005 L_{n}^{[6]} + 8575 L_{n - 1}^{[6]} + 2695 L_{n - 2}^{[6]} - 7385 L_{n - 3}^{[6]} - 24665 L_{n - 4}^{[6]} + 92810 L_{n - 5}^{[6]}) \\ = & \frac{2401 L_{n}^{[6]} + 1715 L_{n - 1}^{[6]} + 539 L_{n - 2}^{[6]} - 1477 L_{n - 3}^{[6]} - 4933 L_{n - 4}^{[6]} + 18562 L_{n - 5}^{[6]}}{205937} \end{array}$
となります。 $k = 6$ のときの分母に現れる $205937$ は素数なこともあって、とても実用的とは言えなさそうですね。

証明

　上で $k$ -リュカ数を $k$ -ナッチ数で表したときを思い出すと、 $α = α_{1}, α_{2}, \dots, α_{k}$ に対し $\frac{1}{f^{'} (α)}$ を負の冪を許した $α$ についての多項式で表せればよいことになります。つまりは以下の等式を示します。

$\frac{1}{f^{'} (α)} = \frac{k - 1}{2 (2 k)^{k} - (k + 1)^{k + 1}} (\sum_{j = 1}^{k - 1} (k + 1)^{k - 1 - j} ((k + 1)^{j} - 2 (2 k)^{j - 1}) α^{- j + 1} + \frac{2 ((2 k)^{k - 1} - (k + 1)^{k - 1})}{k - 1} α^{- k + 1})$

　まず
$\begin{aligned} (x - 1) f (x) & = x^{k + 1} - 2 x^{k} + 1 \\ ((x - 1) f (x))^{'} & = x^{k} ((k + 1) x - 2 k) \\ (α - 1) f^{'} (α) & = α^{k - 1} ((k + 1) α - 2 k) \end{aligned}$
より
$\frac{1}{f^{'} (α)} = \frac{1}{α^{k - 1}} \cdot \frac{α - 1}{(k + 1) α - 2 k}$
が成り立ち、また $\frac{1}{(k + 1) α - 2 k}$ の有理化を考えると
$\begin{array}{rcl} \frac{1}{(k + 1) α - 2 k} & = & - \frac{1}{\prod_{j = 1}^{k} (2 k - (k + 1) α_{j})} \cdot \frac{\prod_{j = 1}^{k} (2 k - (k + 1) α_{j})}{2 k - (k + 1) α} \\ = & - \frac{1}{(k + 1)^{k} f (\frac{2 k}{k + 1})} \cdot \frac{(k + 1)^{k - 1} f (\frac{2 k}{k + 1})}{\frac{2 k}{k + 1} - α} \end{array}$
となるので、このそれぞれの因子を具体的に計算してみましょう。

$(k + 1)^{k} f (\frac{2 k}{k + 1}) = \frac{(k + 1)^{k + 1} - 2 (2 k)^{k}}{k - 1}$

$(x - 1) f (x) = x^{k + 1} - 2 x^{k} + 1$
に注意すると
$\begin{array}{rcl} (k + 1)^{k} f (\frac{2 k}{k + 1}) & = & (k + 1)^{k} \frac{(\frac{2 k}{k + 1})^{k + 1} - 2 (\frac{2 k}{k + 1})^{k} + 1}{\frac{2 k}{k + 1} - 1} \\ = & \frac{(2 k)^{k + 1} - 2 (k + 1) (2 k)^{k} + (k + 1)^{k + 1}}{2 k - (k + 1)} \\ = & \frac{(k + 1)^{k + 1} - 2 (2 k)^{k}}{k - 1} \end{array}$
とわかる。

$\frac{(k + 1)^{k - 1} f (\frac{2 k}{k + 1})}{\frac{2 k}{k + 1} - α} = \frac{1}{α - 1} (\sum_{j = 1}^{k - 1} (k + 1)^{j - 1} ((k + 1)^{k - j} - 2 (2 k)^{k - 1 - j}) α^{j} + \frac{2 ((2 k)^{k - 1} - (k + 1)^{k - 1})}{k - 1})$

　これは以下の補題から直ちに得られます。

$\frac{f (x)}{x - α} = \frac{1}{α - 1} (\sum_{j = 1}^{k - 1} (x^{k - j} - 2 x^{k - j - 1} + 1) α^{j} + (1 - \frac{x^{k} - 2 x^{k - 1} + 1}{x - 1}))$

$\frac{f (x)}{x - α} = \sum_{j = 0}^{k - 1} c_{j} x^{j}$
とおくと
$f (x) = (x - α) \frac{f (x)}{x - α} = x^{k} - \sum_{j = 0}^{k - 1} x^{j}$
より $c_{k - 1} = 1, c_{j - 1} - α c_{j} = - 1$ つまり $c_{j}$ は
$c_{j} = α^{k - j - 1} - \sum_{i = 0}^{k - j - 2} α^{i} = \frac{α^{k - j} - 2 α^{k - j - 1} + 1}{α - 1}$
と求められる。よって
$\begin{array}{rcl} (α - 1) \frac{f (x)}{x - α} & = & \sum_{j = 0}^{k - 1} (α^{j + 1} - 2 α^{j} + 1) x^{k - j - 1} \\ = & (α^{k} + \sum_{j = 1}^{k - 1} α^{j} x^{k - j}) - 2 (\sum_{j = 1}^{k - 1} α^{j} x^{k - j - 1} + x^{k - 1}) + \sum_{j = 0}^{k - 1} x^{k - j - 1} \\ = & \sum_{j = 1}^{k - 1} α^{j} + \sum_{j = 1}^{k - 1} (x^{k - j} - 2 x^{k - j - 1}) α^{j} - 2 x^{k - 1} + \frac{x^{k} - 1}{x - 1} \\ = & \sum_{j = 1}^{k - 1} (x^{k - j} - 2 x^{k - j - 1} + 1) α^{j} + 1 - \frac{x^{k} - 2 x^{k - 1} + 1}{x - 1} \end{array}$
を得る。

　以上より命題1が得られ、冒頭で公式1を導出したのと同様にして公式2を得る。
　ちなみに $α^{k} = 1 / (2 - α)$ から
$\frac{1}{f^{'} (α)} = \frac{α (2 - α)}{- (k + 1)^{k} f (\frac{2 k}{k + 1})} \cdot \frac{(k + 1)^{k - 1} (α - 1) f (\frac{2 k}{k + 1})}{\frac{2 k}{k + 1} - α}$
とも表せるので $k$ -ナッチ数を $k$ -リュカ数の $n$ 以降の項の線形結合で表すこともできるが補題3を見てわかるようにとても煩雑になるのであまりお勧めはしない。