發新話題
打印

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

推到噗浪
推到臉書

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

引用:
費式數列(Fibonacci Numbers):1,2,3,5,8,13,21,34......
試証所有正整數n都可表成不重複的費式數的和。
費式數列(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 中不重複選取之和。

TOP

發新話題