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

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

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

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

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

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

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

　　　　${\displaystyle \begin{array}{rl}& (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^{2}b+3a{b}^2+b^3)-(a^3-3a^{2}b+3a{b}^2-b^3)=6a^{2}b+2b^3\\ & ⋮\\ & (a+b{)}^n-(a-b{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^{n-k}{b}^k-\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^{n-k}(-b{)}^k=2\sum _{k=0}^{\lfloor \frac{n-1}{2}\rfloor }(\genfrac{}{}{0ex}{}{n}{2k+1})a^{n-2k-1}{b}^{2k+1}\end{array}}$

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

　　　　${\displaystyle \begin{array}{rl}{F}_n& =\frac{1}{\sqrt{5}}\{{\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\}\\ & =\frac{1}{2^n\sqrt{5}}\{{\left(1+\sqrt{5}\right)}^n-{\left(1-\sqrt{5}\right)}^n\}\\ & =\frac{1}{2^n\sqrt{5}}\cdot 2\sum _{k=0}^{\lfloor \frac{n-1}{2}\rfloor }(\genfrac{}{}{0ex}{}{n}{2k+1}){\left(\sqrt{5}\right)}^{2k+1}\\ & =\frac{1}{2^{n-1}}\sum _{k=0}^{\lfloor \frac{n-1}{2}\rfloor }(\genfrac{}{}{0ex}{}{n}{2k+1})5^k\end{array}}$

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

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