k-ナッチ数列の四捨五入表示についての考察(ほぼ証明)
はじめに
この記事は
apu_yokai
氏の
フィボナッチ数列を拡張したk-ナッチ数列の一般項についての予想
ひいては
(その2)
に触発されて私なりに考察をした記事になります。
ある程度self-containdに書くつもりなので少し冗長になるかもしれませんがご了承ください。
まずk-ナッチ数列とは以下の漸化式で定義される数列のことを言うのでした。
自然数$k$に対してk-ナッチ数列$\{a_n\}_{n=0}^\infty$を
漸化式$a_0=a_1=\cdots=a_{k-2}=0,\;a_{k-1}=1$
$a_{n+k}=a_{n+k-1}+a_{n+k-2}+\cdots+a_{n}\quad(n\geq0)$
で定める。
そしてk-ナッチ数列の一般項は以下のように求められるのでした。
方程式$f(x)=x^k-x^{k-1}-x^{k-2}-\cdots-x-1=0$の異なる$k$個の解を$\beta_1,\beta_2,\ldots,\beta_k$とおいたとき
$\displaystyle a_n=\sum^k_{j=1}\frac{\beta_k^n}{f'(\beta_k)}$
が成り立つ。
このことについてはapu_yokai氏の
フィボナッチ数を一般化したk-ナッチ数の一般項
等を参照してください。
そしてこの解のうち正の実数であるものがただ一つ存在し、それを$\a$とおくと以下の事実が成り立つことが予想されています。
$x$の四捨五入$\lfloor x+\frac12\rfloor$を$\lfloor x\rceil$で表したとき、
$\displaystyle a_n=\s{\frac{\a^n}{f'(\a)}}$
が成り立つ。
また$\beta_1,\beta_2,\ldots,\beta_k$については以下の評価ができることが知られています。
$\beta_1,\beta_2,\ldots,\beta_k$のうちの一つ$\a$は$1<\a<2$を満たし、
その他の$k-1$個の$\beta$については$|\beta|<1$となる。
このことについてはapu_yokai氏の フィボナッチ数列を拡張したk-ナッチ数列の一般項についての予想(その2) 等を参照してください。
さてこれらの事実を用いて私はk-ナッチ数の四捨五入表示の予想について考察してみたところ、少なくともほとんど全ての自然数$n$について上記の四捨五入表記が成り立つことが確認できました。(私の計算が間違っていなければ)
ちなみにまだ未確認なのは$k+1\leq n\leq 2k-2$のケースのみです。これらのケースについては有志に任せることとします。
以下で私の考察の結果を$0\leq n\leq k$の場合と$2k-1\leq n$の場合に分けて説明していきます。
補題
まず本題に入る前にちょっとだけ補題を示しておきます。
方程式$f(x)=x^k-x^{k-1}-x^{k-2}-\cdots-x-1=0$の任意の解$\beta$について
$\displaystyle\beta^k=\frac{1}{2-\beta}$
が成り立つ。
これは
$\displaystyle f(x)=x^k-\frac{x^k-1}{x-1}=\frac{x^{k+1}-2x^k+1}{x-1}$
つまり
$\beta^k(\beta-2)+1=0$
であることからわかります。
$\displaystyle f'(\beta)=\frac{(k+1)\beta-2k}{\beta(2-\beta)(\beta-1)}$
が成り立つ。
これは
$((x-1)f(x))'=f(x)+(x-1)f'(x)=(k+1)x^k-2kx^{k-1}$
より
$\displaystyle f'(\beta)=\frac{\big((k+1)\beta-2k\big)\beta^k}{\beta(\beta-1)}$
であることから補題3と合わせてわかります。
方程式$f(x)=0$の正の実数解を$\a$とおくと$f'(\a)>0$である。
特に$(k+1)\a-2k>0$が成り立つ。
上で紹介した通り正の実数解はただ一つしかないのでグラフ$y=f(x)$の形状を考えると$x=\a$において$f(x)$は単調増加でなければならない。つまり$f'(\a)>0$となる。
また$1<\a<2$(定理2)から$\a(2-\a)(\a-1)>0$であるので補題4より$(k+1)\a-2k>0$を得る。
$\a>2^{1-\frac1k}$ひいては$\a>2(1-2^{-k})$が成り立つ。
先と同様にグラフ$y=f(x)$の形状を考えると$f(2^{1-\frac1k})<0$であれば$\a>2^{1-\frac1k}$が成り立つ。
いま$2^{\frac1k}-1>\frac1k\log2,\;\log2>\frac12(cf.\;2^2>e)$に注意すると
$(2^{1-\frac1k}-1)f(2^{1-\frac1k})
=2^{k-\frac1k}-2^k+1
=-2^{k-\frac1k}(2^{\frac1k}-1)+1
<1-2^{k-1}\frac{1}{2k}$
であって$k\leq2^{k-2}$は$k\geq4$において成り立つので$f(2^{1-\frac1k})<0$を得る。($k\leq3$のときは別途計算でもすればよい。)
また$\a^{k+1}-2\a^k+1=0$を$\a^k$で割って適当に移項させると
$\a=2-\a^{-k}>1-\a^{-(k-1)}=2(1-2^{-k})$
を得る。
$0\leq n\leq k$のとき
$0\leq n\leq k$においては$k$によらず
$a_0=a_1=\cdots=a_{k-2}=0,\;a_{k-1}=a_k=1$
であることから直接求めます。(一応$a_{k+1}=2$とかも確定ですが面倒なので割愛)
つまり$f'(\a)>0$および$1<\a$であることに注意すると以下のことを示せばよい。
$\displaystyle\frac{\a^{k-2}}{f'(\a)}<\frac12,\quad\frac12\leq\frac{\a^{k-1}}{f'(\a)},\quad\frac{\a^k}{f'(\a)}<\frac32$
が成り立つ。
またapu_yokai氏の
この記事
から$\a$が$k$について単調増加であること、そしてまた別の
この記事
から$k=3$において$\a=1.83\ldots>\sqrt{3}$であることがわかっているので$k\geq3$において
$\displaystyle\frac{\a^k}{f'(\a)}<\frac32$
がわかれば
$\displaystyle\frac{\a^{k-2}}{f'(\a)}=\frac{\a^k}{f'(\a)}\cdot\frac{1}{\a^2}<\frac{3}{2\a^2}<\frac12$
もわかる。$k=2$のときは単純な計算で示せるので以下$k\geq3$として不等式
$\displaystyle\frac12\leq\frac{\a^{k-1}}{f'(\a)},\quad\frac{\a^k}{f'(\a)}<\frac32$
を示す。
補題3,4から
$\displaystyle\frac{\a^{k-1}}{f'(\a)}=\frac{\a-1}{(k+1)\a-2k}$
であってまた$\a<2$より
$((k+1)\a-2k)-2(\a-1)=(k-1)(\a-2)<0$
なので
$\displaystyle\frac12<\frac{\a-1}{(k+1)\a-2k}=\frac{\a^{k-1}}{f'(\a)}$
を得る。
上と同様にして
$\displaystyle\frac{\a^k}{f'(\a)}=\frac{\a(\a-1)}{(k+1)\a-2k}$
であるので不等式
$2\a(\a-1)-3((k+1)\a-2k)=2\a^2-(3k+5)\a+6k<0$
を示せばよい。
いま二次関数$g(x)=2x^2-(3k+5)x+6k$は
$\displaystyle x=\frac{3k+5}{4}>\frac{3+5}{2}=2$
において頂点をとり、また
$g(2-2x)=8x^2+6(k-1)x-2$
$\displaystyle g(2-2\cdot2^{-k})=(\frac{8}{4^k}-\frac12)+(\frac{6(k-1)}{2^k}-\frac32)<0+0$
なので補題6から$2(2-2^{-k})<\a<2$であることに注意すると$g(\a)<0$がわかる。
以上より$0\leq n\leq k$において
$\displaystyle a_n=\s{\frac{\a^n}{f'(\a)}}$
が成り立つことが示された。
$2k-1\leq n$のとき
$2k-1\leq n$のときは直接$\frac{\a^n}{f'(\a)}$の値を評価するのではなく誤差項
$\displaystyle a_n-\frac{\a^n}{f'(\a)}=\sum_{\beta\neq\a}\frac{\beta^n}{f'(\beta)}$
の絶対値が$\frac12$未満であることを示す。
$|\beta|<1$に注意すると具体的には以下の評価が示せればよい。
$\displaystyle\left|\frac{\beta^{2k-1}}{f'(\beta)}\right|<\frac{1}{2(k-1)}$が成り立つ。
まず
$\displaystyle\frac{\beta^{2k-1}}{f'(\beta)}=\frac{1-\beta}{(2-\beta)(2k-(k+1)\beta)}=\frac{1-\beta}{(2-\beta)^2}\cdot\frac{2-\beta}{2k-(1+k)\beta}$
であって$|\beta|<1$ひいては$|2-\beta|>1$に注意すると
$\displaystyle\left|\frac{2-\beta}{2k-(1+k)\beta}\right|\leq\frac{|2-\beta|}{|2k-k\beta|-|\beta|}<\frac{|2-\beta|}{k|2-\beta|-1}<\frac{1}{k-1}$
が成り立つのであとは次のことを言えばよい。
$\displaystyle\left|\frac{1-\beta}{(2-\beta)^2}\right|<\frac12$が成り立つ。
$\beta=r(\cos\theta+i\sin\theta)\quad(0< r<1)$と極形式に表し、
$\displaystyle h(x)=\frac{r^2-2rx+1}{(r^2-4rx+4)^2}\quad(-1\leq x\leq1)$とおく。
このとき
$\displaystyle\left|\frac{1-\beta}{(2-\beta)^2}\right|=\sqrt{h(\cos\theta)}$
となるので$h(x)$の値を評価すればよい。
いま
$\displaystyle h'(x)=\frac{-2r(r^2-4rx+4)+2\cdot4r(r^2-2rx+1)}{(r^2-4rx+4)^3}=\frac{2r^2(3r-4x)}{(r^2-4rx+4)^3}$
なので$h(x)$は$x=\frac34r$において最大値
$\displaystyle h(\frac34r)=\frac{2r^2-3r^2+2}{2(r^2-3r^2+4)}=\frac{1}{8(2-r^2)}$
を取り、また$0< r<1$から
$\displaystyle h(\frac34r)<\frac{1}{8(2-1^2)}$
つまり
$\displaystyle\left|\frac{1-\beta}{(2-\beta)^2}\right|<\frac{1}{\sqrt{8}}<\frac12$
を得る。
以上より$2k-1\leq n$において
$\displaystyle\left|a_n-\frac{\a^n}{f'(\a)}\right|\leq\sum_{\beta\neq\a}|\beta|^{n-(2k-1)}\left|\frac{\beta^{2k-1}}{f'(\beta)}\right|<(k-1)\cdot\frac{1}{2(k-1)}=\frac12$
が成り立つことが示された。
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
