例題：數學歸納法 及 Fibonacci 數列
[quote]費式數列(Fibonacci Numbers):1,2,3,5,8,13,21,34......試証所有正整數n都可表成不重複的費式數的和。
[/quote]
費式數列(Fibonacci Numbers):1,2,3,5,8,13,21,34......
把這些數列各分別稱作是 f[size=1]1[/size],f[size=1]2[/size],f[size=1]3[/size],f[size=1]4[/size],f[size=1]5[/size],f[size=1]6[/size],f[size=1]7[/size],f[size=1]8[/size]...
先觀察一些現象
觀察一：
[size=4][size=2][size=4]對任何[/size] [/size][size=4]n [/size]≧3, [size=2][size=4]f[/size]n[/size][size=4]=f[/size][size=2]n-1 [/size]+ [size=2][size=4]f[/size]n-2 ＞[size=4]f[/size][size=2]n-1 [/size][/size][/size][size=4]且 已知 f[size=1]2[/size]＞f[/size][size=1]1[/size]
[size=4]所以任何 [size=4]n [/size]≧2, [size=2][size=4]f[/size]n [/size][size=2]＞[size=4]f[/size][size=2]n-1 [/size][/size][/size]
[size=4]（寫了這麼多廢話只是為了說，這是一個嚴格遞增數列啦）[/size]
觀察二：
[size=4]對任何 [/size][size=4]n ≧3, [/size][size=2][size=4]2*f[/size][size=2]n-1 [/size][/size][size=4]= f[size=2]n-1 [size=4]+f[/size][size=2]n-1 [/size][/size][/size][size=2]＞[size=2] [size=2][size=4]f[/size][size=2]n-1 [size=4]+f[/size][size=2]n-2[size=4]=f[/size]n [/size][/size][/size][/size][/size]
[size=4] (↑不等號的理由是上面的觀察一)[/size]
[size=4]把 2*f[size=2]n-1 [/size][size=2]＞[size=2] [size=2][size=2][size=2][size=4]f[/size]n [/size][/size][/size][/size][/size]兩邊同時減 f[size=2]n-1 [/size][/size][size=4]可得 f[size=2][size=1]n-1[/size] [/size][size=2]＞[size=2] [size=2][size=2][size=2][size=4]f[size=1]n[/size]－f[/size][/size][/size][/size][/size][/size][/size][size=1]n-1[/size]
觀察三：
對任何正整數 n ，[color=red]如果 n = f[size=1]i[/size],[/color] for some i
那也[color=red]就直接得証命題[/color]啦。
也就是說，我們真正要證的是
[color=red][b]當 f[size=1]i[/size]< n <f[size=1]i+1[/size], for some i ，則 n 可以表示成此 f[size=1]1[/size],f[size=1]2[/size],...,f[size=1]i[/size] 中不重複選取之和。[/b][/color]
好吧，那就用數學歸納法証明好了。
就從有缺數字的 f3～f4 ( i=3 的時候 )開始好了。
第一步：當 i = 3 的時候，對任意自然數 n 滿足 f3＜n＜ f4，則 3＜n＜ 5，可得 n = 4 ，且 n = 4 = 1+3 = f[size=1]1[/size]+f[size=1]3[/size] ， n 可以表示成 f[size=1]1[/size],f[size=1]2[/size],f[size=1]3[/size]中不重複選取之和。
第二步：假設，對任意自然數 i＝3,...,k[size=4] ，對任何自然數 n ，[/size]當 f[size=1]i[/size]< n <fi[size=1]+1[/size], for some i ，則 n 可以表示成此 f[size=1]1[/size],f[size=1]2[/size],...,f[size=1]i[/size] 中不重複選取之和。
則當 i=k+1 時，對[size=4]任何自然數 n 滿足 [size=4]f[/size][size=1]k+1[/size][size=2][size=4]< n <f[/size][/size][/size][size=1]k+2[/size][size=4]，[/size]
[size=4]n=f[size=1]k+1 [/size][/size][size=4]+ （n－f[size=1]k+1[/size]）[/size]
[size=4] ^^^^^^^^∵觀察二及 f[size=1]k+1[/size][size=2][size=4]< [b]n <f[/b][/size][/size][size=1][b]k+2 [/b][size=4]，所以（n－f[size=1]k-1[/size]）[/size][/size]< f[/size][size=1]k+1[/size][size=4]恆成立。[/size]
[size=4]故 （n－f[size=1]k-1[/size]）= f[size=2]i[/size], for some 1≦i≦k 或是 [/size]
[size=4]f[size=1]i[/size]<（n－f[/size][size=1]k-1[/size][size=4]）<f[size=1]i+1[/size], for some i =3,...,k 由歸納法假設，可知 （n－f[size=1]k-1[/size]）可以表示成此 f[size=1]1[/size],f[size=1]2[/size],...,f[/size][size=1]i[/size][size=4] 中不重複選取之和。[/size]
[size=4]故 n=f[size=1]k+1 [/size][size=4]+ （n－f[size=1]k+1[/size]）可以表示成此 f[size=1]1[/size],f[size=1]2[/size],...,f[size=1]k [/size][size=4]及[/size]f[size=1]k+1[/size][size=4] 中不重複選取之和。[/size][/size][/size]
由第一步＆第二步，及數學歸納法可知 [color=red][b]當 f[size=1]i[/size]< n <f[size=1]i+1[/size], for some i ，則 n 可以表示成此 f[size=1]1[/size],f[size=1]2[/size],...,f[size=1]i[/size] 中不重複選取之和。[/b][/color]
頁:
[1]