文献あり

k-ナッチ数列の四捨五入表示についての考察(ほぼ証明)

208

はじめに

　この記事は apu_yokai 氏のフィボナッチ数列を拡張したk-ナッチ数列の一般項についての予想ひいては (その2) に触発されて私なりに考察をした記事になります。
　ある程度self-containdに書くつもりなので少し冗長になるかもしれませんがご了承ください。
　まずk-ナッチ数列とは以下の漸化式で定義される数列のことを言うのでした。

k-ナッチ数列

　自然数 $k$ に対してk-ナッチ数列 ${a_{n}}_{n = 0}^{\infty}$ を
$a_{0} = a_{1} = \dots = a_{k - 2} = 0, a_{k - 1} = 1$
および漸化式
$a_{n + k} = a_{n + k - 1} + a_{n + k - 2} + \dots + a_{n} (n \geq 0)$
によって定める。

　そしてk-ナッチ数列の一般項は以下のように求められるのでした。

k-ナッチ数列の一般項

　多項式
$f (x) = x^{k} - x^{k - 1} - x^{k - 2} - \dots - x - 1$
の異なる $k$ 個の根を $β_{1}, β_{2}, \dots, β_{k}$ とおいたとき
$a_{n} = \sum_{j = 1}^{k} \frac{β_{k}^{n}}{f^{'} (β_{k})}$
が成り立つ。

　このことについてはapu_yokai氏のフィボナッチ数を一般化したk-ナッチ数の一般項等を参照してください。
　そしてこの解のうち正の実数であるものがただ一つ存在し、それを $α$ とおくと以下の事実が成り立つことが予想されています。

k-ナッチ数の四捨五入表示

　 $x$ の四捨五入 $⌊ x + \frac{1}{2} ⌋$ を $⌊ x ⌉$ で表したとき、
$a_{n} = ⌊ \frac{α^{n}}{f^{'} (α)} ⌉$
が成り立つ。

　また $β_{1}, β_{2}, \dots, β_{k}$ については以下の評価ができることが知られています。

　 $β_{1}, β_{2}, \dots, β_{k}$ のうちの一つ $α$ は $1 < α < 2$ を満たし、その他の $k - 1$ 個の $β$ については $| β | < 1$ となる。

　このことについてはapu_yokai氏のフィボナッチ数列を拡張したk-ナッチ数列の一般項についての予想(その2) 等を参照してください。
　さてこれらの事実を用いて私はk-ナッチ数の四捨五入表示の予想について考察してみたところ、少なくともほとんど全ての自然数 $n$ について上記の四捨五入表記が成り立つことが確認できました(私の計算が間違っていなければ)。
　ちなみにまだ未確認なのは $k + 1 \leq n \leq 2 k - 2$ のケースのみです。これらのケースについては有志に任せることとします。
　以下で私の考察の結果を $0 \leq n \leq k$ の場合と $2 k - 1 \leq n$ の場合に分けて説明していきます。

補題

　まず本題に入る前にちょっとだけ補題を示しておきます。

　方程式
$f (x) = x^{k} - x^{k - 1} - x^{k - 2} - \dots - x - 1 = 0$
の任意の解 $β$ について
$β^{k} = \frac{1}{2 - β}$
が成り立つ。

$f (x) = x^{k} - \frac{x^{k} - 1}{x - 1} = \frac{x^{k + 1} - 2 x^{k} + 1}{x - 1}$
つまり
$β^{k} (β - 2) + 1 = 0$
が成り立つことからわかる。

$f^{'} (β) = \frac{(k + 1) β - 2 k}{β (2 - β) (β - 1)}$
が成り立つ。

$\begin{aligned} ((x - 1) f (x))^{'} & = f (x) + (x - 1) f^{'} (x) \\ = (k + 1) x^{k} - 2 k x^{k - 1} \end{aligned}$
つまり
$f^{'} (β) = \frac{((k + 1) β - 2 k) β^{k}}{β (β - 1)}$
が成り立つから補題3と合わせてわかる。

　方程式 $f (x) = 0$ の正の実数解を $α$ とおくと $f^{'} (α) > 0$ が成り立つ。特に $(k + 1) α - 2 k > 0$ が成り立つ。

　上で紹介した通り正の実数解はただ一つしかないのでグラフ $y = f (x)$ の形状を考えると $x = α$ において $f (x)$ は単調増加でなければならない。つまり $f^{'} (α) > 0$ となる。
　また $1 < α < 2$ (定理2)から $α (2 - α) (α - 1) > 0$ が成り立つので補題4より $(k + 1) α - 2 k > 0$ を得る。

　 $α > 2^{1 - \frac{1}{k}}$ ひいては $α > 2 (1 - 2^{- k})$ が成り立つ。

　先と同様にグラフ $y = f (x)$ の形状から
$x < α ⟺ f (x) < 0$
が成り立つことに注意すると $f (2^{1 - \frac{1}{k}}) < 0$ を示せばよい。
　いま
$2^{\frac{1}{k}} - 1 > \frac{1}{k} \log 2 > \frac{1}{2 k}$
に注意すると
$\begin{aligned} (2^{1 - \frac{1}{k}} - 1) f (2^{1 - \frac{1}{k}}) & = 2^{k - \frac{1}{k}} - 2^{k} + 1 \\ = 1 - 2^{k - \frac{1}{k}} (2^{\frac{1}{k}} - 1) \\ < 1 - 2^{k - 1} \frac{1}{2 k} \end{aligned}$
であって $k \leq 2^{k - 2}$ は $k \geq 4$ において成り立つので $f (2^{1 - \frac{1}{k}}) < 0$ を得る( $k \leq 3$ のときは別途計算でもすればよい)。
　また $α^{k + 1} - 2 α^{k} + 1 = 0$ を $α^{k}$ で割って適当に整理することで
$α = 2 - α^{- k} > 2 - (2^{1 - \frac{1}{k}})^{- k} = 2 (1 - 2^{- k})$
を得る。

$0 \leq n \leq k$ のとき

　 $0 \leq n \leq k$ においては $k$ によらず
$a_{0} = a_{1} = \dots = a_{k - 2} = 0, a_{k - 1} = a_{k} = 1$
であることから直接求めます(一応 $a_{k + 1} = 2$ とかも確定ですが面倒なので割愛)。
　つまり $f^{'} (α) > 0$ および $1 < α$ であることに注意すると以下のことを示せばよい。

$\frac{α^{k - 2}}{f^{'} (α)} < \frac{1}{2}, \frac{1}{2} \leq \frac{α^{k - 1}}{f^{'} (α)}, \frac{α^{k}}{f^{'} (α)} < \frac{3}{2}$
が成り立つ。

　またapu_yokai氏のこの記事から $α$ が $k$ について単調増加であること、そしてまた別のこの記事から $k = 3$ において $α = 1.83 \dots > \sqrt{3}$ であることがわかっているので $k \geq 3$ において
$\frac{α^{k}}{f^{'} (α)} < \frac{3}{2}$
がわかれば
$\frac{α^{k - 2}}{f^{'} (α)} = \frac{α^{k}}{f^{'} (α)} \cdot \frac{1}{α^{2}} < \frac{3}{2 α^{2}} < \frac{1}{2}$
も自動的に導かれる。
　したがって以下 $k \geq 3$ として不等式
$\frac{1}{2} \leq \frac{α^{k - 1}}{f^{'} (α)}, \frac{α^{k}}{f^{'} (α)} < \frac{3}{2}$
を示していく( $k = 2$ のときは単純な計算で示せる)。

\frac{1}{2} \leq \frac{α^{k - 1}}{f^{'} (α)}

　補題3,4から
$\frac{α^{k - 1}}{f^{'} (α)} = \frac{α - 1}{(k + 1) α - 2 k}$
が成り立つので $α < 2$ より
$((k + 1) α - 2 k) - 2 (α - 1) = (k - 1) (α - 2) < 0$
と評価できることに注意すると
$\frac{1}{2} < \frac{α - 1}{(k + 1) α - 2 k} = \frac{α^{k - 1}}{f^{'} (α)}$
を得る。

\frac{α^{k}}{f^{'} (α)} < \frac{3}{2}

　上と同様に
$\frac{α^{k}}{f^{'} (α)} = \frac{α (α - 1)}{(k + 1) α - 2 k}$
が成り立つので不等式
$2 α (α - 1) - 3 ((k + 1) α - 2 k) = 2 α^{2} - (3 k + 5) α + 6 k < 0$
を示せばよい。
　いま二次関数 $g (x) = 2 x^{2} - (3 k + 5) x + 6 k$ は
$x = \frac{3 k + 5}{4} > \frac{3 + 5}{2} = 2$
において頂点を取る、特に $x < 2$ において単調減少であり、また
$\begin{aligned} g (2 - 2 x) & = 8 x^{2} + 6 (k - 1) x - 2 \\ g (2 - 2 \cdot 2^{- k}) & = (\frac{8}{4^{k}} - \frac{1}{2}) + (\frac{6 (k - 1)}{2^{k}} - \frac{3}{2}) < 0 + 0 \end{aligned}$
が成り立つので $2 (2 - 2^{- k}) < α < 2$ であったことに注意すると $g (α) < 0$ を得る。

　以上より $0 \leq n \leq k$ において
$a_{n} = ⌊ \frac{α^{n}}{f^{'} (α)} ⌉$
が成り立つことが示された。

$2 k - 1 \leq n$ のとき

　 $2 k - 1 \leq n$ のときは主要項 $\frac{α^{n}}{f^{'} (α)}$ の値を評価するのではなく誤差項
$a_{n} - \frac{α^{n}}{f^{'} (α)} = \sum_{β \neq α} \frac{β^{n}}{f^{'} (β)}$
の絶対値が $\frac{1}{2}$ 未満であることを示す。
　 $| β | < 1$ に注意すると具体的には以下の評価を示せばよい。

$| \frac{β^{2 k - 1}}{f^{'} (β)} | < \frac{1}{2 (k - 1)}$
が成り立つ。

　まず $| β | < 1$ ひいては $| 2 - β | > 1$ から
$| \frac{2 - β}{2 k - (1 + k) β} | \leq \frac{| 2 - β |}{| 2 k - k β | - | β |} < \frac{| 2 - β |}{k | 2 - β | - 1} < \frac{1}{k - 1}$
が成り立つので
$\frac{β^{2 k - 1}}{f^{'} (β)} = \frac{1 - β}{(2 - β) (2 k - (k + 1) β)} = \frac{1 - β}{(2 - β)^{2}} \cdot \frac{2 - β}{2 k - (1 + k) β}$
であったことに注意すると次のことを言えばよい。

$| \frac{1 - β}{(2 - β)^{2}} | < \frac{1}{2}$
が成り立つ。

$β = r (\cos θ + i \sin θ) (0 < r < 1)$
と極形式に表し
$h (x) = \frac{r^{2} - 2 r x + 1}{(r^{2} - 4 r x + 4)^{2}} (- 1 \leq x \leq 1)$
とおくと
$| \frac{1 - β}{(2 - β)^{2}} | = \sqrt{h (\cos θ)}$
が成り立つ。
　また
$\begin{aligned} h^{'} (x) & = \frac{- 2 r (r^{2} - 4 r x + 4) + 2 \cdot 4 r (r^{2} - 2 r x + 1)}{(r^{2} - 4 r x + 4)^{3}} \\ = \frac{2 r^{2} (3 r - 4 x)}{(r^{2} - 4 r x + 4)^{3}} \end{aligned}$
より $h (x)$ は $x = \frac{3}{4} r$ において最大値
$\begin{aligned} h (\frac{3}{4} r) & = \frac{2 r^{2} - 3 r^{2} + 2}{2 (r^{2} - 3 r^{2} + 4)} = \frac{1}{8 (2 - r^{2})} \\ < \frac{1}{8 (2 - 1^{2})} = \frac{1}{8} \end{aligned}$
を取るので
$| \frac{1 - β}{(2 - β)^{2}} | < \frac{1}{\sqrt{8}} < \frac{1}{2}$
を得る。

　以上より $2 k - 1 \leq n$ において
$\begin{aligned} | a_{n} - \frac{α^{n}}{f^{'} (α)} | & \leq \sum_{β \neq α} | β |^{n - (2 k - 1)} | \frac{β^{2 k - 1}}{f^{'} (β)} | \\ < (k - 1) \cdot \frac{1}{2 (k - 1)} = \frac{1}{2} \end{aligned}$
が成り立つことが示された。