フィボナッチ数列の和

フィボナッチ数列

\begin{eqnarray}
F_0&=&0\\
F_1&=&1\\
F_n&=&F_{n-1}+F_{n-2}
\end{eqnarray}

すなわち $F_n$ は直前2項の和となる。実際に計算してみる。

\begin{eqnarray}
F_2&=&F_0+F_1=0+1=1\\
F_3&=&F_1+F_2=1+1=2\\
F_4&=&1+2=3\\
F_5&=&2+3=5\\
F_6&=&3+5=8
\end{eqnarray}

その和

この数列の $n$ 項目までの和、 $\sum_{k=0}^{n} F_k$ はどんな形になるだろうか？実際に $F_k$ を足し合わせてみると、

\begin{eqnarray}
F_0&=&F_0\\
F_1&=&F_1\\
F_2&=&F_0+F_1\\
F_3&=&F_1+F_2\\
\cdots\\
F_{n-1}&=&F_{n-3}+F_{n-2}\\
F_n&=&F_{n-2}+F_{n-1}\\
\\
\displaystyle \sum_{k=0}^{n} F_k &=& 2F_0+3F_1+2F_2+2F_3+ \cdots +F_{n-1}
\end{eqnarray}

…この計算だとあまり単純にならない。やり直し。

上手く $F_n$ を引き算の形で表せば、上式で係数が2のところは全部消えそう。まずフィボナッチ数列の $n+2$ 項目を考えると、

\begin{equation} F_{n+2}=F_n+F_{n+1} \end{equation}

移項して $F_n$ を引き算で表す。

\begin{equation} F_{n}=F_{n+2}-F_{n+1} \end{equation}

この形で辺々足し合わせていく。

\begin{eqnarray} \require{cancel} F_0&=& \cancel{F_2}-F_1\\
F_1&=&\cancel{F_3}-\cancel{F_2}\\
F_2&=&\cancel{F_4}-\cancel{F_3}\\
F_3&=&\cancel{F_5}-\cancel{F_4}\\
\cdots\\
F_{n-1}&=&\cancel{F_{n+1}}-\cancel{F_n}\\
F_n&=&F_{n+2}-\cancel{F_{n+1}}\\
\\
\displaystyle \sum_{k=0}^{n} F_k &=& F_{n+2}-F_1\\
&=&\underline{F_{n+2}-1}
\end{eqnarray}
フィボナッチ級数の単純な形が求められた。