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

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

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}