裴波那契數(shù)列!
遞推公式：F(n+2) = F(n+1) + F(n)
其通式的推導較為復雜：
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為二次方程 x^2 - 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)為等比數(shù)列,G(n) = b^n ,即
F(n+1) - aF(n) = G(n) = b^n --------(1)
在(1)式中分別將上述 a b的兩組解代入,由于對稱性不妨設x = (1 + √5)/2,y = (1 -√5)/2,得到：
F(n+1) - xF(n) = y^n
F(n+1) - yF(n) = x^n
以上兩式相減得：
(x-y)F(n) = x^n - y^n
F(n) = (x^n - y^n)/(x-y) = {[(1+√5)/2]^n-[(1-√5)/2]^n}/√5
有關裴波那契數(shù)列的問題,可參考