2007年3月28日 星期三

費氏數列的特性(續)

看到Barrosh寫的”雜記”,證明了之前在”費氏數列的特性”提到的問題:

F(kn)會是F(n)的倍數

參考Barrosh的想法,想到類似的簡單證明,基本精神一樣。

將F(n)、F(n+1)的表示改寫成F(n)和F(n-1)的組合:

F(n) = 1*F(n) + 0*F(n-1)
F(n+1) = 1*F(n) + 1*F(n-1)

觀察右式的F(n)和F(n-1),得知可以將F(k)、k >= n視為兩組費氏數列的和,兩組費氏數列的基數分別為F(n)和F(n-1)。

更一般化地表示如下:

F(n) = F(1)*F(n) + F(0)*F(n-1)
F(n+1) = F(2)*F(n) + F(1)*F(n-1)

所以F(2n) = F(n+1)*F(n) + F(n)*F(n-1) = (F(n+1)+F(n-1)) * F(n)

套用數學歸納法:

  1. k = 1時,F(n)成立
  2. 假設F(kn) = a*F(n)成立,k >= 1
  3. F((k+1)n) = F(kn+1)*F(n) + F(kn)*F(n-1) = (F(kn+1)+a*F(n-1))*F(n) 亦成立(得證)

ps

用線性代數的觀點也許會更容易理解,對F(k)、k >= n來說,F(k)可以看成F(n)和F(n-1)的線性組合,將原本基數為 1 、一維的F(k),轉到基數為F(n)和F(n-1)的二維的空間。

沒有留言:

張貼留言