例題：數學歸納法　及　Fibonacci 數列

費式數列(Fibonacci Numbers):1,2,3,5,8,13,21,34......
把這些數列各分別稱作是　　f1,f2,f3,f4,f5,f6,f7,f8...

先觀察一些現象

觀察一：
對任何 n ≧3, fn=fn-1 + fn-2 ＞fn-1 且 已知 f2＞f1
所以任何 n ≧2, fn ＞fn-1 　
（寫了這麼多廢話只是為了說，這是一個嚴格遞增數列啦）

觀察二：
對任何 n ≧3, 2*fn-1 = fn-1 +fn-1 ＞ fn-1 +fn-2=fn
　　　　　　　　　　　　　(↑不等號的理由是上面的觀察一)
把 2*fn-1 ＞ fn 兩邊同時減 fn-1 可得 fn-1 ＞ fn－fn-1

觀察三：
對任何正整數 n ，如果 n = fi, for some i
那也就直接得証命題啦。
也就是說，我們真正要證的是
當 fi< n <fi+1, for some i ，則 n 可以表示成此 f1,f2,...,fi 中不重複選取之和。

好吧，那就用數學歸納法証明好了。

就從有缺數字的 f3～f4 ( i=3 的時候 )開始好了。

第一步：當 i = 3 的時候，對任意自然數 n 滿足 f3＜n＜ f4，則 3＜n＜ 5，可得 n = 4 ，且 n = 4 = 1+3 = f1+f3 ， n 可以表示成 f1,f2,f3中不重複選取之和。

第二步：假設，對任意自然數 i＝3,...,k ，對任何自然數 n ，當 fi< n <fi+1, for some i ，則 n 可以表示成此 f1,f2,...,fi 中不重複選取之和。
則當 i=k+1 時，對任何自然數 n 滿足 fk+1< n <fk+2，
n=fk+1　+　（n－fk+1）
　　　　　^^^^^^^^∵觀察二及 fk+1< n <fk+2 ，所以（n－fk-1）< fk+1恆成立。

故 （n－fk-1）= fi, for some 1≦i≦k 或是
fi<（n－fk-1）<fi+1, for some i =3,...,k 由歸納法假設，可知 （n－fk-1）可以表示成此 f1,f2,...,fi 中不重複選取之和。
故 n=fk+1　+　（n－fk+1）可以表示成此 f1,f2,...,fk 及fk+1 中不重複選取之和。

由第一步＆第二步，及數學歸納法可知 當 fi< n <fi+1, for some i ，則 n 可以表示成此 f1,f2,...,fi 中不重複選取之和。