4

フィボナッチ数の一般項のカタランの公式の導出

192
0
$$$$

この記事ではフィボナッチ数の一般項を表す式たちのうち、「カタランの公式」と呼ばれているものを紹介します。

フィボナッチ数の一般項(カタランの公式)

    ${\displaystyle F_n=\frac{1}{2^{n-1}} \sum_{k=0}^{\left\lfloor \frac{n-1}{2} \right\rfloor} {n \choose 2k+1} 5^k }$

この公式はフィボナッチ数列のもつ周期性を調べるときに使います。
ビネの公式では式の中に無理数( $\sqrt{5}$ )が出てきますが、カタランの公式には無理数が出てこないので、フィボナッチ数列のもつ周期性を調べるときにはカタランの公式の方が便利なのです。

(参考:フィボナッチ数の一般項を表すいろいろな表現についてはこちらもご覧ください。)
いろいろな方法でフィボナッチ数の一般項を表現する

カタランの公式の導出にはビネの公式を使います。

フィボナッチ数の一般項(ビネの公式)

    ${\displaystyle F_{n}={\frac {1}{\sqrt {5}}}\left\{\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right\}}$

(参考:ビネの公式の導出についてはこちらもご覧ください。)
フィボナッチ数の一般項の四捨五入による表現の導出
フィボナッチ数を一般化したk-ナッチ数の一般項

まず、こんな式変形を考えます。
途中に出てくる ${\displaystyle{n \choose k}}$ の記号は二項係数です。

    ${\displaystyle \begin{align} &(a+b)-(a-b)=2b\\ &(a+b)^2-(a-b)^2=(a^2+2ab+b^2)-(a^2-2ab+b^2)=4ab\\ &(a+b)^3-(a-b)^3=(a^3+3a^2b+3ab^2+b^3)-(a^3-3a^2b+3ab^2-b^3)=6a^2b+2b^3\\ &\qquad\vdots\\ &(a+b)^n-(a-b)^n=\sum_{k=0}^{n}{n \choose k}a^{n-k}b^k-\sum_{k=0}^{n}{n \choose k}a^{n-k}(-b)^k=2\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}{n \choose 2k+1}a^{n-2k-1}b^{2k+1} \end{align} }$

ビネの公式のカッコの中を上記のように二項係数を使って展開すると、 $\sqrt{5}$を含む項が打ち消しあって消えます。

    ${\displaystyle \begin{align} F_{n}&={\frac {1}{\sqrt {5}}}\left\{\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right\}\\ &={\frac {1}{2^n\sqrt {5}}}\left\{\left({1+{\sqrt {5}}}\right)^{n}-\left({1-{\sqrt {5}}}\right)^{n}\right\}\\ &={\frac {1}{2^n\sqrt {5}}}\cdot2\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} {n \choose 2k+1}\left(\sqrt{5}\right)^{2k+1}\\ &={\frac {1}{2^{n-1}}}\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} {n \choose 2k+1}5^k\\ \end{align} }$

できました!
検算してみましょう

検算

    ${\displaystyle \begin{align} F_{1} &={\frac {1}{1}}\cdot {1 \choose 1}=1\\ F_{2} &={\frac {1}{2}} \cdot{2 \choose 1}=1\\ F_{3} &={\frac {1}{4}}\left( {3 \choose 1}+{3 \choose 3}\cdot5\right)=2\\ F_{4} &={\frac {1}{8}}\left( {4 \choose 1}+{4 \choose 3}\cdot5\right)=3\\ F_{5} &={\frac {1}{16}}\left( {5 \choose 1}+{5 \choose 3}\cdot5+{5 \choose 5}\cdot5^2\right)=5\\ F_{6} &={\frac {1}{32}}\left( {6 \choose 1}+{6 \choose 3}\cdot5+{6 \choose 5}\cdot5^2\right)=8\\ F_{7} &={\frac {1}{64}}\left( {7 \choose 1}+{7 \choose 3}\cdot5+{7 \choose 5}\cdot5^2+{7 \choose 7}\cdot5^3\right)=13\\ \qquad\vdots \end{align} }$

確かにフィボナッチ数になっていますね!

投稿日:20201121

この記事を高評価した人

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

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

バッジはありません。

投稿者

apu_yokai
apu_yokai
440
53156

コメント

他の人のコメント

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