費氏數列的特性（續）

看到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)的二維的空間。