フィボナッチ数列の加法定理

by nomura · 2024年12月9日

フィボナッチ数列の加法定理
$m,n\in\mathbb{Z}$とする。
フィボナッチ数列について次の式が成り立つ。
\[ F_{m+n}=F_{m-1}F_{n}+F_{m}F_{n+1} \]

-

$F_{n}$はフィボナッチ数列

$n=0$のとき、

任意の$m\in\mathbb{Z}$に対し、$F_{m}=F_{m-1}F_{0}+F_{m}F_{0+1}=F_{m}$なので明らかに成り立つ。

$n=k+1$のとき、

$n=k$のとき成り立つと仮定すると、
\begin{align*} \left[F_{m+n}\right]_{n=k+1} & =F_{m+\left(k+1\right)}\\ & =F_{\left(m+1\right)+k}\\ & =F_{m}F_{k}+F_{m+1}F_{k+1}\\ & =F_{m}F_{k}+\left(F_{m}+F_{m-1}\right)F_{k+1}\\ & =F_{m-1}F_{k+1}+F_{m}\left(F_{k}+F_{k+1}\right)\\ & =F_{m-1}F_{k+1}+F_{m}F_{k+2} \end{align*} となるので$n=k+1$のときも成り立つ。

$n=k-1$のとき、

\begin{align*} \left[F_{m+n}\right]_{n=k-1} & =F_{m+\left(k-1\right)}\\ & =F_{\left(m-1\right)+k}\\ & =F_{m-2}F_{k}+F_{m-1}F_{k+1}\\ & =\left(F_{m}-F_{m-1}\right)F_{k}+F_{m-1}F_{k+1}\\ & =F_{m}F_{k}+F_{m-1}\left(-F_{k}+F_{k+1}\right)\\ & =F_{m}F_{k}+F_{m-1}F_{k-1} \end{align*} となるので$n=k-1$のときも成り立つ。