斐波那契数列通项公式推导

· · 个人记录

前言

令f[i](i ≥0)表示斐波那契数的第i项。

是人都知道：f[0]=0，f[1]=1，f[n]=f[n-1]+f[n-2](n≥2)

但是如何求他的通项公式呢，有些两岁小朋友就不知道了。

求斐波那契数列通项公式的方法

我们用"待定系数法"推导。

设常数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*s^{n-2}+r^2*s^{n-3}+\dots+r^{n-1}

根据等比数列求和公式(这是一个以s^{n-1}为首项，r^{n-1}为末项，\dfrac{r}{s}为公比的等比数列）可得：

f[n]=\dfrac{s^{n-1}-r^{n-1}*\dfrac{r}{s}}{1-\dfrac{r}{s}} f[n]=\dfrac{s^n-r^n}{s-r}

因为：r+s=1,-rs=1的一组解为：

\begin{cases}s=\dfrac{1+\sqrt{5}}{2}\\r=\dfrac{1-\sqrt{5}}{2}\end{cases}

带入可得：

f[n]=\dfrac{\sqrt{5}}{5}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right]