フィボナッチ数の一般項のカタランの公式の導出
この記事ではフィボナッチ数の一般項を表す式たちのうち、「カタランの公式」と呼ばれているものを紹介します。
${\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} }$
確かにフィボナッチ数になっていますね!
この記事を高評価した人
この記事に送られたバッジ
投稿者
