2

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

108
0
$$$$

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

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

フィボナッチ数の一般項の四捨五入を使った表現

   $F_n=\left\lfloor\frac{\varphi^n}{\sqrt{5}}\right\rceil$

ただし、$\varphi$は次の定数です。
    $\begin{align} \varphi&=\frac{1+\sqrt{5}}{2}\\ &=1.618033988749894\cdots \end{align}$

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

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

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

母関数を閉じた式にする

$ \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} }$

誤差項を評価する

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

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

第2項を評価すると
        ${\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} }$
導出できました!

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

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

投稿日:20201113

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

apu_yokai
apu_yokai
457
57553

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中