A(n+2)=pA(n+1)+qAn,p,q為常數 （1）通常設：A(n+2)-mA(n+1)=k[A(n+1)-mAn], 則 m+k=p,mk=-q （2）特徵根法： 特徵方程是y²=py+q（※） 注意：① m n為（※）兩根. ② m n可以交換位置,但其結果或出現兩種截然不同的數列形式,但同樣都可以計算

斐波那契數列：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}