費氏數列的算法。

Question

費氏數列的通式：F(n)= 1 / √5 * {[ ( 1+ √5 ) / 2 ]^n - [ ( 1 - √5 ) / 2 ]^n}
請問F(20) = 6765如何用紙筆算出來呢？不是用電腦程式去run出來的哦！

Answer 1

這倒是不必照定義慢慢加，不過也不需要用到矩陣那麼高階的方法。(事實上我也不會矩陣)有一個比較初等的重要公式可用，它會變形唷！f(m+n)=f(m+1)f(n)+f(m)f(n-1)http://tw.knowledge.yahoo.com/question/?qid=1306031510698令m=n-1代入得到f(2n-1)=f(n)2+f(n-1)2計算奇數項時用，右式是連續兩項平方和。令m=n代入得到f(2n)=f(n+1)f(n)+f(n)f(n-1)計算偶數項時用，右式是連續三項之前兩項乘積加後兩項乘積。利用這兩個公式，我們可以以比較小的項次算出比較大的項次之值。f(20)=f(9)f(10)+f(10)f(11)=34*55+55*89=1870+4895=6765

2006-11-30 22:18:11 補充：
當然數字也不能太大，否則也簡便不到哪裡去像f(40)就已經很麻煩了，f(19)=f(9)^2+f(10)^2=4181f(20)=f(9)f(10)+f(10)f(11)=6765f(21)=4181+6765=10946f(40)=f(19)f(20)+f(20)f(21)=102334155

Answer 2

令 A=
[ 1 1 ]
``1 0
則 [F(n+2), F(n+1)]^(t)= A [F(n+1),F(n)]^(t)
所以 [F(n+2), F(n+1)]^(t)= ( A^18) [ F(2), F(1) ]^(t)
A^3 =
[ 3 2 ]
``2 1
A^6 =
[ 13 8 ]
`` 8 5
A^18= (A^6)^ 3 =
[4181, 2584]
`* , *
又 [F(2), F(1)]=[1,1]
所以 F(20)=6765!

Answer 3

如果只是要算第20項，直接照定義算，應該還ok～
如果一定要用Binet 公式，用些小技巧應該還好，大家試試看喔～