フィボナッチ数列： f (n)　　　f ²(n) ＋ f ²(n＋1) ＝ f (2n＋1)　の証明

n	1	2	3	4	5	6	7	8	9
f (n)	1	1	2	3	5	8	13	21	4
f 2(n)	1	1	4	9	25	64	169	441	1156

　まず、次の式を証明します。
　　　f (m＋n) ＝ f (m−1) f (n) ＋ f (m) f (n＋1)　　（ ただし m ＞ 1 ）　　・・・ �@

　n ＝ 1　のとき、
　　　f (m＋1) ＝ f (m−1) ＋ f (m)
　　　　　　　 ＝ f (m−1) f (1) ＋ f (m) f (2)　　・・・ �A
　　　よって、�@ は成り立つ。

　n ＝ 2　のとき、
　　　f (m＋2) ＝ f (m) ＋ f (m＋1)
　　　　　　　 ＝ f (m) ＋ f (m−1) ＋ f (m)
　　　　　　　 ＝ f (m−1) ＋ 2 f (m)
　　　　　　　 ＝ f (m−1) f (2) ＋ f (m) f (3)　　・・・ �B
　　　よって、�@ は成り立つ。

　一般に n ＝ k　のとき、�@ が成り立つと仮定する。つまり、次の式が成り立つとする。
　　　f (m＋k) ＝ f (m−1) f (k) ＋ f (m)　 f (k＋1)　　・・・ �C
　一般に n ＝ k＋1　のとき、�@ が成り立つと仮定する。つまり、次の式が成り立つとする。
　　　　f (m＋k＋1) ＝ f (m−1) f (k＋1) ＋ f (m) f (k＋2)　　・・・ �D

　すると、 n ＝ k＋2　のとき、
　　　　f (m＋k＋2) ＝ f (m＋k＋1) ＋ f (m＋k)
　　　　　　　　　＝ ( f (m−1) f (k) ＋ f (m) f (k＋1) )　＋　( f (m−1) f (k＋1) ＋ f (m) f (k＋2) )
　　　　　　　　　＝ f (m−1) ( f (k＋1) ＋ f (k) )　＋　f (m) ( f (k＋2) ＋ f (k＋1) )
　　　　　　　　　＝ f (m−1) f (k＋2) ＋ f (m) f (k＋3)
　　　というわけで、式�@ が成り立つことがわかった。

　�Aと�Bより、 n ＝ 1　のとき と n ＝ 2　のとき、式�@ が成り立つことがわかっている。
　 n ＝ 1　のとき 式�@ が成り立つのだから、 n ＝ 3　のときも 式�@ が成り立つ。
　 n ＝ 2　のとき 式�@ が成り立つのだから、 n ＝ 4　のときも 式�@ が成り立つ。
　 n ＝ 3　のとき 式�@ が成り立つのだから、 n ＝ 5　のときも 式�@ が成り立つ。
　 n ＝ 4　のとき 式�@ が成り立つのだから、 n ＝ 6　のときも 式�@ が成り立つ。
　同様にして、式�@ はすべての n について成り立つことが分かる。
　こうして、式�@ は証明された。

　次に、式�@ に　m = a+1　n = a　を代入します。すると、次のようになります。
　　　f (2a＋1) ＝ f (a) f (a) ＋ f (a+1) f (a＋1)
　　　　　　　 ＝ f ²(a) ＋ f ²(a＋1)
　　　　　　　　　　　　　　　　　　　　　（ 証明終わり ）