費氏數列的特性（續）
March 28th, 2007
看到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)
套用數學歸納法：
- k = 1時，F(n)成立
- 假設F(kn) = a*F(n)成立，k >= 1
- 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)的二維的空間。
呵！沒想到會被發現….XD
的確，既然 費氏數列 是遞迴定義，我們很直覺地會想展開到以基項 (F(1)) 來表示。同理，直覺上，既然是遞迴，對任意項 F(n) 來說，凡是 s>n， F(s) 應該也都可以展開到以 F(n) 表示。
不過，問題是在展開式中各項的係數的計算。以 費氏數列 這種簡單(但有趣) 的遞迴關係來說，很巧的，它的係數剛好也是 費氏數列。
這大概是這個問題的有趣之處吧。否則去算 費氏數列 還真是件無聊的事…..XD 算是有趣的國中數學阿，哈….Orz
附帶一提，組合數學最不需要數學基礎吧。用線性代數的觀點去看反而更複雜，何況它並不是 vector space，雖然可以看成某兩項的組合，但是這個組合也不算是線性組合。是否會有混淆之虞？
的確有混淆之虞 XD
我沒修過組合數學，想必應該有更好的表示方式，只是有時會想，如果能用vector space表示，會有什麼特性呢？還沒抓到轉換的精神，有時候轉過去結果相當易懂，像是用vector space表示least square。
總覺得線性代數是很妙的數學，什麼東西都想試著用線代體會看看，而忽略了適不適合。現在線代也都忘光了 Orz