A4の宇宙

数学と物理をA4ノートに収まる範囲で。

フィボナッチ数列の和

フィボナッチ数列

以下の数列をフィボナッチ数列と呼ぶ。

\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}
フィボナッチ級数の単純な形が求められた。

 

検算

\begin{eqnarray}
\displaystyle \sum_{k=0}^{4} F_k &=& F_{6}-F_1 = 8-1=7\\
\displaystyle \sum_{k=0}^{4} F_k &=& 0+1+1+2+3=7
\end{eqnarray}

一致している。