費氏數列的特性 (3)

延伸這篇以費氏數列表示費氏數列的想法，可以找出費氏數列和巴斯卡三角形的關係。我沒仔細讀WikiPedia上的說明，好像有些差異，單純自high地記錄找到的關係。

將費氏數列拆成費氏數列的和，並用vector表示各項費氏數列係數的話，容易觀察出巴斯卡三角的特性，這裡只是示意表示，最左邊的欄位表示F(n)的係數，左邊數來第二欄表示F(n-1)的係數，以此類推：

F(n) = [1, 0]
F(n) = [0, 1, 1]
F(n) = [0, 0, 1, 2, 1]
F(n) = [0, 0, 0, 1, 3, 3, 1]
F(n) = [0, 0, 0, 0, 1, 4, 6, 4, 1]

舉例來說，F(n)可以看成 1*F(n-4) + 4*F(n-5) + 6*F(n-6) + 4*F(n-7) + 1*F(n-8)，以 n = 9代入為例，即為34 = 1*5 + 4*3 + 6*2 + 4*1 + 1*1。

費氏數列的特性（續）

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

費氏數列的特性

昨天看《數學高手特訓班》時，裡面提到證明費氏數列的特性：F(5n)會是F(5)的倍數，我花幾分鐘證出後，回頭看書，作者描述的對象(國中生)在幾分鐘後，回答的是：

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

這就是數學強者和弱者的等級差異啊。

ps：列出前20項F(n)給大家參考

F(1)：1
F(2)：1
F(3)：2
F(4)：3
F(5)：5
F(6)：8
F(7)：13
F(8)：21
F(9)：34
F(10)：55
F(11)：89
F(12)：144
F(13)：233
F(14)：377
F(15)：610
F(16)：987
F(17)：1597
F(18)：2584
F(19)：4181
F(20)：6765

ps 2：我對F(5n)會是F(5)的倍數的的冗長證明

key point：把F(n)表示成 5a + 3b，僅需討論 3b 的變化，b介於 0 ~ 4 之間。下面列出 b 的變化，證明每20項發生循環。

F(6) ~ F(10)：(1, 1, 2, 3, 0)
F(11) ~ F(15)：(3, 3, 1, 4, 0)
F(16) ~ F(20)：(4, 4, 3, 2, 0)
F(21) ~ f(25)：(2, 2, 4, 1, 0)