フィボナッチ数の一般項の四捨五入による表現の導出

フィボナッチ数の一般項の四捨五入による表現

この記事ではフィボナッチ数を$F_n$で表します。
まず、過去記事で紹介した四捨五入による表現を紹介します。
なお、四捨五入する関数としてこの記事では $\lfloor x\rceil$ という記法を使います。すなわち
　　　　$\lfloor x\rceil=\left\lfloor x+\frac{1}{2}\right\rfloor$
ということです。

導出過程はこの記事↓
テトラナッチ数列の一般項を求める
と同じですので、詳細はそちらを参照してください。

(実はもっと簡単な導出方法もあるのですが、次の記事では同様の方法でトリボナッチ数列の一般項を求めるつもりなのでこの方法を使います。)

以下では概略のみ記載します。

母関数を閉じた式にする

$ \begin{align} F(x)&=F_0 x^0+F_1 x^1 + F_2 x^2+F_3x^3 + F_4 x^4 +F_5x^5+F_6x^6+F_7x^7+F_8x^8+\cdots\\ &=0+ 1x+ 1x^2+ 2x^3+ 3x^4+ 5x^5+ 8x^6+ 13x^7+ 21x^8+\cdots\\ &=x+ x^2+ 2x^3+ 3x^4+ 5x^5+ 8x^6+ 13x^7+ 21x^8+\cdots\\ \end{align} $

　　　　$ \begin{array}{c} F(x)&=&x+&x^2+&2x^3+ &3x^4+ &5x^5+ &8x^6+\cdots\\ xF(x)&=&&x^2+& x^3+ &2x^4+ &3x^5+& 5x^7+\cdots\\ x^2F(x)&=&&&x^3+ &x^4+ &2x^5+ &3x^6+ \cdots\\ \end{array} $

　　　　$ (1-x-x^2)F(x)=x $
　　　　$ \therefore F(x)=\frac{x}{1-x-x^2} $

部分分数分解して無限級数化する

　　$x$の方程式 $1-x-x^2=0$の2つの解を $\alpha,\beta$ として、
　　　　${\displaystyle \begin{align} F(x)&=\frac{x}{1-x-x^2}\\ &=\frac{-x}{(x-\alpha)(x-\beta)}\\ &=\frac{-x}{x-\alpha}\cdot\frac{1}{(\alpha-\beta)} +\frac{-x}{x-\beta}\cdot\frac{1}{(\beta-\alpha)}\\ &=\frac{x}{1-\frac{x}{\alpha}}\cdot\frac{1}{\alpha(\alpha-\beta)} +\frac{x}{1-\frac{x}{\beta}}\cdot\frac{1}{\beta(\beta-\alpha)}\\ &=\sum_{n=0}^{\infty}x^{n+1}\left( \frac{1}{\alpha^{n+1}(\alpha-\beta)} +\frac{1}{\beta^{n+1}(\beta-\alpha)}\right) \\ \end{align} } $

ここで　${\displaystyle F(x)=\sum_{n=0}^{\infty}F_n x^n }$　だったことを思い出して上記の式と係数比較すると、

　　　　${\displaystyle \begin{align} F_n&= \frac{1}{\alpha^{n}(\alpha-\beta)}+\frac{1}{\beta^{n}(\beta-\alpha)} \\ \end{align} }$

ここまで$x$の方程式 $1-x-x^2=0$の2つの解を $\alpha,\beta$ として計算してきましたが、$x=\frac{1}{t}$と置換して $t$の方程式　$t^2-t-1=0$の解を $t=\varphi,\bar{\varphi}$　とすると、$\alpha=\frac{1}{\varphi},\beta=\frac{1}{\bar{\varphi}}$ と書き換えることができます。
　　　　$\varphi=\frac{1+\sqrt{5}}{2}=1.618\cdots,\bar{\varphi}=\frac{1-\sqrt{5}}{2}=0.618\cdots$
とすれば、
　　　　${\displaystyle \begin{align} F_n&= \frac{\varphi^{n}}{(\frac{1}{\varphi}-\frac{1}{\bar{\varphi}})} +\frac{\bar{\varphi}^{n}}{(\frac{1}{\bar{\varphi}}-\frac{1}{\varphi})}\\ &= \frac{\varphi^{n}}{\sqrt{5}} -\frac{\bar{\varphi}^{n}}{\sqrt{5}}\\ \end{align} }$

誤差項を評価する

得られた式を観察すると、第１項は公比 $\varphi$ の等比数列、第２項は公比 $\bar{\varphi}$ の等比数列となっていることがわかります。

　　　　${\displaystyle \begin{align} F_n &= \underbrace{\frac{\varphi^{n}}{\sqrt{5}}}_{\text{第１項}} -\underbrace{\frac{\bar{\varphi}^{n}}{\sqrt{5}}}_{\text{第２項}}\\ \end{align} }$

第２項を評価すると
　　　　　　　　${\displaystyle \begin{align} \left| \frac{\bar{\varphi}^{n}}{\sqrt{5}}\right| &\le\left| \frac{\bar{\varphi}^{0}}{\sqrt{5}}\right|\\ &=\frac{1}{\sqrt{5}}\\ &<\frac{1}{2} \end{align} }$

となります。ここで
　　　　${\displaystyle \begin{align} \frac{\varphi^{n}}{\sqrt{5}} =F_n+\frac{\bar{\varphi}^{n}}{\sqrt{5}}\\ \end{align} }$

なのでこの式の両辺を四捨五入すると
　　　　${\displaystyle \begin{align} \left\lfloor \frac{\varphi^{n}}{\sqrt{5}}\right\rceil &=\left\lfloor F_n+\frac{\bar{\varphi}^{n}}{\sqrt{5}}\right\rceil \\ &=F_n\qquad\qquad\because \left| \frac{\bar{\varphi}^{n}}{\sqrt{5}}\right| <\frac{1}{2} \end{align} }$

　　　　${\displaystyle \begin{align} \therefore F_n=\left\lfloor \frac{\varphi^{n}}{\sqrt{5}}\right\rceil \end{align} }$
導出できました!

「予想」との関係

この式は
フィボナッチ数列を拡張したk-ナッチ数列の一般項についての予想
の、$k=2$ の場合の式と一致しています!

補足

　　　　${\displaystyle \begin{align} F_n &= \underbrace{\frac{\varphi^{n}}{\sqrt{5}}}_{\text{第１項}} -\underbrace{\frac{\bar{\varphi}^{n}}{\sqrt{5}}}_{\text{第２項}}\\ \end{align} }$
この式をよく見ると、$n$が大きいときは第２項がほとんどゼロになることから、第１項がほとんど整数になることがわかります。無理数の等比数列なのに、$n$が大きくなるほどどんどん整数に近づくなんて面白いですね!