フィボナッチ数が現れる問題（１３）の解答例を示します。
（１３）の解
数学的帰納法で示す。
（Ａ）n=1の場合、明らか。
（Ｂ）n=kのとき、成り立つとすると、n=k+1のときも成り立つ。
（Ａ),(Ｂ）より、証明された。
この関係を利用すると、f(n)を効率よく求めることができる。
より、行列の積は加算４回、乗算８回が必要。
例えば、f(1025)を求めるには、漸化式では、加算が1024回必要。
行列積を使うと、
A(2)=A(1)A(1)
A(4)=A(2)A(2)
A(8)=A(4)A(4)
A(16)=A(8)A(8)
A(32)=A(16)A(16)
A(64)=A(32)A(32)
A(128)=A(64)A(64)
A(256)=A(128)A(128)
A(512)=A(256)A(256)
A(1024)=A(512)A(512)
と計算すればよく、行列積10回でよい。
したがって、加算10×4=40回、乗算10×8=80回となる。
加算と乗算の計算時間を同一と仮定すると、120/1024で、約1/10と改善される。
また、A(m+n)=A(m)A(n)の関係から、
f(m+n+1)=f(m+1)f(n+1)+f(m)f(n) (m≧1,n≧1)
が導かれる。
