フィボナッチ数列 $\set{u_n}_{n \in \NN \cup \set{0}}$は

\[\begin{align} u_0 = 0, u_1 = 1, \\ u_{n + 2} = u_n + u_{n + 1} \end{align}\]

で定義されました.

このとき, 以下の主張が成り立ちます:

定理(フィボナッチ数列の加法定理): 自然数$m, n$に対して $$ u_{m + n} = u_m u_{n-1} + u_{m+1} u_n $$ が成り立つ.

証明: $n$に関する数学的帰納法で示します.

$n=1$のとき, 主張は

\[u_{m+1} = u_mu_0 + u_{m+1}u_1\]

となります. $u_0=0, u_1=1$なので, 確かにこれは成り立ちます.

$n=2$のとき, 主張は

\[\begin{align} u_{n+2} &= u_mu_1 + u_{m+1}u_2 \\ &= u_m + u_{m+1} \end{align}\]

なので, これも成り立っている.

$n = k > 2$のとき:

数学的帰納法の仮定より, 以下の二式が成り立っています:

\[\begin{align} u_{m+k} &= u_mu_{k-1} + u_{m+1}u_k, \\ u_{m+k-1} &= u_mu_{k-2} + u_{m+1}u_{k-1}. \end{align}\]

したがって, この二式を足すと

\[u_{m+k+1} = u_mu_k + u_{m+1}u_{k+1}\]

が成り立つことが分かります.