祖宗十八代查询:斐波拉契数列问题

F(n)= (1/√5){[(1+√5)/2]^(n+2)-[(1-√5)/2]^(n+2)}

下面用特征值法求F(n)——裴波那契数列 1 1 2 3 5 ... 的通项

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

令 F(n+2) - aF(n+1) = b(F(n+1) - aF(n))
展开 F(n+2) - (a+b)F(n+1) + abF(n) = 0
显然 a+b = 1 ab = -1
由韦达定理知 a、b为二次方程 x2 - x - 1 = 0 的两个根
解得 a = (1 + √5)/2，b = (1 -√5)/2 或 a = (1 -√5)/2，b = (1 + √5)/2

令G(n) = F(n+1) - aF(n)，则G(n+1) = bG(n)，且G(1) = F(2) - aF(1) = 1 - a = b，因此G(n)为等比数列，G(n) = (1-a)bn-1 = bn ，即
F(n+1) - aF(n) = G(n) = bn -------------------------------------- (1)

在(1)式中分别将上述 a b的两组解代入，由于对称性不妨设x = (1 + √5)/2，y = (1 -√5)/2，得到：
F(n+1) - xF(n) = yn
F(n+1) - yF(n) = xn
以上两式相减得：
(x-y)F(n) = xn - yn
F(n) = (xn - yn)/(x-y) = {[(1+√5)/2]n-[(1-√5)/2] n}/√5

A1=1,A2=1,A3=2所以A(n+2)=A(n+1)+A(n)
A1=1
A2=1
A3=A2+A1
A4=A3+A2
…………
A(n-1)=A(n-2)+A(n-3)
A(n)=A(n-1)+A(n-2)
等式左右两边相加得
A1+……+A(n-1)+An=2+A0+2A1+2A2+……+2A(n-2)+A(n-1)

所以，An=2+A2+A3+……+A(n-2)

结果懒得写了，告诉你过程
f(n) = f(n-1) + f(n)
设f(n) - af(n-1) = b(f(n-1) - af(n-2))
则a+b=1 a*b=-1 可以求出a,b
又设g(n) = f(n + 1) - af(n)为等比数列g(n) = bg(n-1)且g(1) = 1-a = b
所以g(n) = b^n
即f(n + 1) = af(n) + b^n
af(n) = a*af(n-1) + a*b^(n-1)
...
a^(n-1)f(2) = a^nf(1) + a^(n-1)*b
相加
f(n+1) = a^n + b^n + ... + a^(n-1) * b
f(n + 1) = a^n+(1-a)*((a/b)^n-1)/(a/b-1) = (a^(n+1) - b^(n+1))/(a-b)
代入a,b在简化