斐波那契數列：1、1、2、3、5、8、13、21、……

如果設F(n)為該數列的第n項(n∈N+).那麼這句話可以寫成如下形式：

F(0) = 0,F(1)=F(2)=1,F(n)=F(n-1)+F(n-2) (n≥3)

顯然這是一個線性遞推數列.

通項公式的推導方法一：利用特徵方程

線性遞推數列的特徵方程為：

X^2=X+1

解得

X1=(1+√5)/2,X2=(1-√5)/2

則F(n)=C1*X1^n + C2*X2^n

∵F(1)=F(2)=1

∴C1*X1 + C2*X2

C1*X1^2 + C2*X2^2

解得C1=1/√5,C2=-1/√5

∴F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}（√5表示根號5）

通項公式的推導方法二：普通方法

設常數r,s

使得F(n)-r*F(n-1)=s*[F(n-1)-r*F(n-2)]

則r+s=1,-rs=1

n≥3時,有

F(n)-r*F(n-1)=s*[F(n-1)-r*F(n-2)]

F(n-1)-r*F(n-2)=s*[F(n-2)-r*F(n-3)]

F(n-2)-r*F(n-3)=s*[F(n-3)-r*F(n-4)]

……

F(3)-r*F(2)=s*[F(2)-r*F(1)]

將以上n-2個式子相乘,得：

F(n)-r*F(n-1)=[s^(n-2)]*[F(2)-r*F(1)]

∵s=1-r,F(1)=F(2)=1

上式可化簡得：

F(n)=s^(n-1)+r*F(n-1)

那麼：

F(n)=s^(n-1)+r*F(n-1)

= s^(n-1) + r*s^(n-2) + r^2*F(n-2)

= s^(n-1) + r*s^(n-2) + r^2*s^(n-3) + r^3*F(n-3)

……

= s^(n-1) + r*s^(n-2) + r^2*s^(n-3) +……+ r^(n-2)*s + r^(n-1)*F(1)

= s^(n-1) + r*s^(n-2) + r^2*s^(n-3) +……+ r^(n-2)*s + r^(n-1)

（這是一個以s^(n-1)為首項、以r^(n-1)為末項、r/s為公差的等比數列的各項的和）

=[s^(n-1)-r^(n-1)*r/s]/(1-r/s)

=(s^n - r^n)/(s-r)

r+s=1,-rs=1的一解為 s=(1+√5)/2,r=(1-√5)/2

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

迭代法

已知a1=1,a2=1,an=a(n-1)+a(n-2)(n>=3),求數列{an}的通項公式

解 :設an-αa(n-1)=β(a(n-1)-αa(n-2))

得α+β=1

αβ=-1

構造方程x?x-1=0,解得α=(1-√5)/2,β=(1+√5)/2或α=(1+√5)/2,β=(1-√5)/2

所以

an-(1-√5)/2*a(n-1)=(1+√5)/2*(a(n-1)-(1-√5)/2*a(n-2))=[(1+√5)/2]^(n-2)*(a2-(1-√5)/2*a1)`````````1

an-(1+√5)/2*a(n-1)=(1-√5)/2*(a(n-1)-(1+√5)/2*a(n-2))=[(1-√5)/2]^(n-2)*(a2-(1+√5)/2*a1)`````````2

由式1,式2,可得

an=[(1+√5)/2]^(n-2)*(a2-(1-√5)/2*a1)``````````````3

an=[(1-√5)/2]^(n-2)*(a2-(1+√5)/2*a1)``````````````4

將式3*(1+√5)/2-式4*(1-√5)/2,化簡得an=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}