第1章 绪论
斐波那契数列为$F_0=0$，$F_1=1$，$F_n=F_{n-1}+F_{n-2}(n\geq 2)$，现通过6种不同的方法求它的通项公式。
第2章 特征方程法
对于$F_0=0$，$F_1=1$，$F_n=F_{n-1}+F_{n-2}(n\geq 2)$，假设解$F_n$的基本形式。
①常数，$F_n=C$。$C=C+C\Rightarrow C=0$，不符。
②一次函数，$F_n=rn+s$，$rn+s=r(n-1)+s+r(n-2)+s\Rightarrow n=3-\frac{s}{r}$，不符。
③三角函数，$F_n=sin(n)$。$sin(n)=sin(n-1)+sin(n-2)$，不符。
④对数函数，$F_n=ln(n)$。$ln(n)=ln(n-1)+ln(n-2)$，不符。
⑤指数函数，$F_n=r^n$。$r^n=r^{n-1}+r^{n-2}\Rightarrow r^2=r+1\Rightarrow r^2-r-1=0$，可能满足。
故猜测$F_n=r^n$，并且$r$满足$r^2-r-1=0$。
$r$有两个解，$r_1=\frac{1+\sqrt{5}}{2}$，$r_2=\frac{1-\sqrt{5}}{2}$。
$F_n$通解即为两个线性无关解的组合。
$$F_n=Ar_1^n+Br_2^n$$
当$n=0$时，$F_0=A+B=0\Rightarrow B=-A$。
当$n=1$时，$F_1=Ar_1+Br_2=1$，带入$B=-A$，得
$$A(r_1-r_2)=1\Rightarrow A=\frac{1}{\sqrt{5}}\Rightarrow B=-\frac{1}{\sqrt{5}}$$
代入$F_n=Ar_1^n+Br_2^n$得，
$$F_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$
代入$n=0$和$n=1$验证，满足条件。
第3章 生成函数法
对于$F_0=0$，$F_1=1$，$F_n=F_{n-1}+F_{n-2}(n\geq 2)$，定义
$$F(x)=\sum_{n=0}^{\infty}F_nx^n=F_0+F_1x+F_2x^2+F_3x^3+…$$
等式两边同时乘$x$，$x^2$，并于原式比较，
$$\begin{aligned}
F(x) &=F_0 + \hspace{-1em}&&F_1x + &&\hspace{-1em}F_2x^2 + &&\hspace{-1em}F_3x^3 + &&\hspace{-1em}…\
x\cdot F(x) &= &&F_0x + &&\hspace{-1em}F_1x^2 + &&\hspace{-1em}F_2x^3 + &&\hspace{-1em}F_3x^4 + &&\hspace{-1em}…\
x^2\cdot F(x)&= && &&\hspace{-1em}F_0x^2 + &&\hspace{-1em}F_1x^3 + &&\hspace{-1em}F_2x^4 + &&\hspace{-1em}F_3x^5 + &&\hspace{-1em}…
\end{aligned}$$
故有，
$$\begin{aligned}
(1-x-x^2)F(x)&=F_0+F_1x-F_0x+\sum_{n=2}^{\infty}(F_n-F_{n-1}-F_{n-2})x^n\
&=F_0+F_1x-F_0x\
&=x
\end{aligned}$$
即，
$$F(x)=\frac{x}{1-x-x^2}$$
尝试将分母$1-x-x^2$因式分解，令
$$1-x-x^2=0$$
解得，
$$x_1=\frac{-1+\sqrt{5}}{2}，x_2=\frac{-1-\sqrt{5}}{2}$$
故有，
$$\begin{aligned}
1-x-x^2=&-\left(x-\frac{-1+\sqrt{5}}{2}\right)\cdot\left(x-\frac{-1-\sqrt{5}}{2}\right)\
=&-\left(\frac{-1+\sqrt{5}}{2}\cdot\frac{-1-\sqrt{5}}{2}\right)\left(x\cdot\frac{2}{-1+\sqrt{5}}-\frac{-1+\sqrt{5}}{2}\cdot\frac{2}{-1+\sqrt{5}}\right)\cdot\
&\left(x\cdot\frac{2}{-1-\sqrt{5}}-\frac{-1-\sqrt{5}}{2}\cdot\frac{2}{-1-\sqrt{5}}\right)\
=&\left(\frac{1+\sqrt{5}}{2}x-1\right)\cdot\left(\frac{1-\sqrt{5}}{2}x-1\right)\
=&\left(1-\frac{1+\sqrt{5}}{2}x\right)\cdot\left(1-\frac{1-\sqrt{5}}{2}x\right)
\end{aligned}$$
设
$$F(x)=\frac{x}{1-x-x^2}=\frac{A}{1-\frac{1+\sqrt{5}}{2}x}+\frac{B}{1-\frac{1-\sqrt{5}}{2}x}$$
通分得，
$$\begin{aligned}
F(x)&=\frac{A\left(1-\frac{1-\sqrt{5}}{2}x\right)+B\left(1-\frac{1+\sqrt{5}}{2}x\right)}{1-x-x^2}\
&=\frac{(A+B)-\left(A\cdot\frac{1-\sqrt{5}}{2}+B\cdot\frac{1+\sqrt{5}}{2}\right)x}{1-x-x^2}\
&=\frac{x}{1-x-x^2}
\end{aligned}$$
可得，$A=\frac{1}{\sqrt{5}}=-B$。
故有，
$$F(x)=\frac{1}{\sqrt{5}}\left[\frac{1}{1-\frac{1+\sqrt{5}}{2}x}-\frac{1}{1-\frac{1-\sqrt{5}}{2}x}\right]$$
由几何级数
$$\frac{1}{1-ax}=\sum_{n=0}^{\infty}a^nx^n$$
得
$$F(x)=\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]x^n$$
与$F(x)=\sum_{n=0}^{\infty}F_nx^n$比较系数，得
$$F_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$
第4章 矩阵法
对于$F_0=0$，$F_1=1$，$F_n=F_{n-1}+F_{n-2}(n\geq 2)$，有
$$\begin{aligned}
F_n &=1\cdot F_{n-1}+1\cdot F_{n_2}\
F_{n-1}&=1\cdot F_{n-1}+0\cdot F_{n_2}
\end{aligned}$$
写成矩阵，
$$\begin{aligned}
\begin{pmatrix}
F_n \
F_{n-1}
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 \
1 & 0
\end{pmatrix}
\begin{pmatrix}
F_{n-1} \
F_{n-2}
\end{pmatrix}
\end{aligned}$$
记
$$M=
\begin{pmatrix}
1 & 1 \
1 & 0
\end{pmatrix}$$
故有
$$\begin{aligned}
\begin{pmatrix}
F_n \
F_{n-1}
\end{pmatrix}
=
M
\begin{pmatrix}
F_{n-1} \
F_{n-2}
\end{pmatrix}
=
M^2
\begin{pmatrix}
F_{n-2} \
F_{n-3}
\end{pmatrix}
=…
=
M^{n-1}
\begin{pmatrix}
F_1 \
F_0
\end{pmatrix}
\end{aligned}$$
代入$F_0=0$，$F_1=1$，
$$\begin{aligned}
\begin{pmatrix}
F_n \
F_{n-1}
\end{pmatrix}
=
M^{n-1}
\begin{pmatrix}
1 \
0
\end{pmatrix}
\end{aligned}$$
不难发现，只需要求出$M^{n-1}$即可求出$F_n$。
计算$M=
\begin{pmatrix}
1 & 1 \
1 & 0
\end{pmatrix}$的特征值与特征向量，
$$\lambda_1=\frac{1+\sqrt{5}}{2}，\lambda_2=\frac{1-\sqrt{5}}{2}$$
$$\begin{aligned}
\varphi_1=
\begin{pmatrix}
\lambda_1 \
1
\end{pmatrix}
，
\varphi_2=
\begin{pmatrix}
\lambda_2 \
1
\end{pmatrix}
\end{aligned}$$
对角化矩阵$M$,
$$M=PDP^{-1}$$
其中，
$$\begin{aligned}
P=
\begin{pmatrix}
\varphi_1 & \varphi_2
\end{pmatrix}
=
\begin{pmatrix}
\lambda_1 & \lambda_2 \
1 & 1
\end{pmatrix}
\end{aligned}$$
$$\begin{aligned}
D=
\begin{pmatrix}
\lambda_1 & 0 \
0 & \lambda_2
\end{pmatrix}
\end{aligned}$$
$$\begin{aligned}
P^{-1}=\frac{1}{\sqrt{5}}
\begin{pmatrix}
1 & -\lambda_2 \
-1 & \lambda_1
\end{pmatrix}
\end{aligned}$$
由对角化的性质，可得
$$\begin{aligned}
M^{n-1}=PD^{n-1}P^{-1}&=\frac{1}{\sqrt{5}}
\begin{pmatrix}
\lambda_1 & \lambda_2 \
1 & 1
\end{pmatrix}
\begin{pmatrix}
\lambda_1^{n-1} & 0 \
0 & \lambda_2^{n-1}
\end{pmatrix}
\begin{pmatrix}
1 & -\lambda_2 \
-1 & \lambda_1
\end{pmatrix}\
&=\frac{1}{\sqrt{5}}
\begin{pmatrix}
\lambda_1^n & \lambda_2^n \
\lambda_1^{n-1} & \lambda_2^{n-1}
\end{pmatrix}
\begin{pmatrix}
1 & -\lambda_2 \
-1 & \lambda_1
\end{pmatrix}
\end{aligned}$$
故有
$$\begin{aligned}
\begin{pmatrix}
F_n \
F_{n-1}
\end{pmatrix}
=
M^{n-1}
\begin{pmatrix}
1 \
0
\end{pmatrix}
&=\frac{1}{\sqrt{5}}
\begin{pmatrix}
\lambda_1^n & \lambda_2^n \
\lambda_1^{n-1} & \lambda_2^{n-1}
\end{pmatrix}
\begin{pmatrix}
1 & -\lambda_2 \
-1 & \lambda_1
\end{pmatrix}
\begin{pmatrix}
1 \
0
\end{pmatrix}\
&=\frac{1}{\sqrt{5}}
\begin{pmatrix}
\lambda_1^n & \lambda_2^n \
\lambda_1^{n-1} & \lambda_2^{n-1}
\end{pmatrix}
\begin{pmatrix}
1 \
-1
\end{pmatrix}\
&=\frac{1}{\sqrt{5}}
\begin{pmatrix}
\lambda_1^n-\lambda_2^n \
\lambda_1^{n-1}-\lambda_2^{n-1}
\end{pmatrix}
\end{aligned}$$
只看第一行，可得
$$F_n=\frac{1}{\sqrt{5}}(\lambda_1^n-\lambda_2^n)$$
即
$$F_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$
第5章 移位算子法
对于$F_0=0$，$F_1=1$，$F_n=F_{n-1}+F_{n-2}(n\geq 2)$，定义移位算子$E$
$$EF_n=F_{n+1}$$
故有
$$E^2F_n=EF_{n+1}=F_{n+2}$$
同理可得，
$$E^kF_n=F_{n+k}$$
同时，也可以看出
$$F_n=E^nF_0=E^n$$
由$F_n=F_{n-1}+F_{n-2}$得
$$F_n=EF_n+E^2F_n\Rightarrow(E^2+E-1)F_n=0$$
由于$F_n$不恒为$0$，故有
$$E^2+E-1=0$$
解方程，得
$$E_1=\frac{1+\sqrt{5}}{2}，E_2=\frac{1-\sqrt{5}}{2}$$
对于特解$E_1$，我们有$F_n=E_1^n$。对于特解$E_2$，我们有$F_n=E_2^n$。
故$E$得通解应为
$$E^n=AE_1^n+BE_2^n$$
当$n=0$时，$F_0=E^0=A+B=0$。
当$n=1$时，$F_1=E^1=AE_1+BE_2$。
可得，$A=\frac{1}{\sqrt{5}}=-B$
故有
$$F_n=E^n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$
第6章 构造等比数列法
对于$F_0=0$，$F_1=1$，$F_n=F_{n-1}+F_{n-2}(n\geq 2)$，假设可以凑出以下形式
$$F_n-pF_{n-1}=q(F_{n-1}-pF_{n-2})$$
并且令
$$G_n=F_n-pF_{n-1}$$
故有
$$G_n=qG_{n-1}$$
这是一个首项$G_0=1$，公比为$q$的等比数列。可以求得
$$G_n=q^{n-1}$$
将凑的式子$F_n-pF_{n-1}=q(F_{n-1}-pF_{n-2})$化简，得
$$F_n=(p+q)F_{n-1}-pqF_{n-2}$$
与$F_n=F_{n-1}+F_{n-2}$对比系数，得
$$\begin{aligned}
\begin{cases}
p + q&=1\
\quad pq&=-1
\end{cases}
\end{aligned}$$
解得
$$\begin{aligned}
\begin{cases}
p=\frac{1+\sqrt{5}}{2}\
q=\frac{1-\sqrt{5}}{2}
\end{cases}
\quad 或\quad
\begin{cases}
p=\frac{1-\sqrt{5}}{2}\
q=\frac{1+\sqrt{5}}{2}
\end{cases}
\end{aligned}$$
令
$$\begin{aligned}
\begin{cases}
s_1=\frac{1+\sqrt{5}}{2}\
s_2=\frac{1-\sqrt{5}}{2}
\end{cases}
\end{aligned}$$
故
$$\begin{aligned}
\begin{cases}
p=s_1\
q=s_2
\end{cases}
\quad 或\quad
\begin{cases}
p=s_2\
q=s_1
\end{cases}
\end{aligned}$$
当$p=s_1，q=s_2$时，有$G_n=F_n-pF_{n-1}=q^{n-1}$，即$F_n-s_1F_{n-1}=s_2^{n-1}①$。
当$p=s_2，q=s_1$时，有$G_n=F_n-pF_{n-1}=q^{n-1}$，即$F_n-s_2F_{n-1}=s_1^{n-1}②$。
$①\cdot s_2-②\cdot s_1$得，$(s_2-s_1)=F_n=s_2^n-s_1^n$，即
$$F_n=\frac{s_2^n-s_1^n}{s_2-s_1}$$
代入$s_1$和$s_2$得
$$F_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$
第7章 无穷连分数法
对于$F_0=0$，$F_1=1$，$F_n=F_{n-1}+F_{n-2}(n\geq 2)$，我们对$F_n=F_{n-1}+F_{n-2}$等式两边同时除以$F_{n-1}$，得
$$\frac{F_n}{F_{n-1}}=1+\frac{F_{n-2}}{F_{n-1}}$$
令
$$x_n=\frac{F_n}{F_{n-1}}$$
故有
$$x_n=1+\frac{1}{x_{n-1}}$$
将上式一直迭代，得
$$x_n=1+\frac{1}{x_{n-1}}=1+\frac{1}{1+\frac{1}{x_{n-2}}}=1+\frac{1}{1+\frac{1}{1+\frac{1}{x_{n-3}}}}=…$$
取极限
$$\varphi=\lim_{n\rightarrow\infty}x_n=1+\frac{1}{1+\frac{1}{1+\frac{1}{\ddots}}}$$
故有
$$\varphi=1+\frac{1}{\varphi}$$
取$\varphi>0$解得
$$\varphi=\frac{1+\sqrt{5}}{2}$$
现在证
$$\varphi^n=\varphi F_n+F_{n-1}$$
成立，用归纳法。
由$\varphi=1+\frac{1}{\varphi}$得，
$$\varphi^2=\varphi+1$$
当$n=1$时，有$\varphi^1=\varphi F_1+F_0$成立；
当$n=k$且$\varphi^{k-1}=\varphi F_{k-1}+F_{k-2}$时，
$$\begin{aligned}
&\varphi^{k-1}=\varphi F_{k-1}+F_{k-2}\
\Rightarrow&\varphi^k=\varphi^2F_{k-1}+\varphi F_{k-2}\
\Rightarrow&\varphi^k=(\varphi+1)F_{k-1}+\varphi F_{k-2}\
\Rightarrow&\varphi^k=\varphi(F_{k-1}+F_{k-2})+F_{k-1}\
\Rightarrow&\varphi^k=\varphi F_k+F_{k-1}
\end{aligned}$$
综上，
$$\varphi^n=\varphi F_n+F_{n-1}$$
成立。
即
$$F_n=\varphi^{n-1}-\varphi^{-1}F_{n-1}$$
继续迭代
$$\begin{aligned}
F_n&=\varphi^{n-1}-\varphi^{-1}(\varphi^{n-2}-\varphi^{-2}F_{n-2})\
&=\varphi^{n-1}-\varphi^{n-3}+\varphi^{-3}F_{n-2}\
&=\varphi^{n-1}-\varphi^{n-3}+\varphi^{n-5}-\varphi^{-5}F_{n-3}\
&=\varphi^{n-1}-\varphi^{n-3}+\varphi^{n-5}-\varphi^{n-7}+\varphi^{-7}F_{n-4}\
&=\varphi^{n-1}-\varphi^{n-3}+\varphi^{n-5}-…-(-1)^n\varphi^{-n+1}+(-1)^n\varphi^{-2n+1}F_0\
&=\varphi^{n-1}-\varphi^{n-3}+\varphi^{n-5}-…-(-1)^n\varphi^{-n+1}\
&=\frac{\varphi^{n-1}[1-(-\varphi^{-2})^n]}{1+\varphi^{-2}}\
&=\frac{\varphi^{n-1}-(-1)^n\varphi^{-n-1}}{1+\varphi^{-2}}\
&=\frac{\varphi^{-1}}{1+\varphi^{-2}}[\varphi^{n}-(-\frac{1}{\varphi})^n]\
\end{aligned}$$
代入$\varphi=\frac{1+\sqrt{5}}{2}$，得
$$F_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$
$，现通过6种不同的方法求它的通项公式。
第2章 特征方程法
对于$F_0=0$，$F_1=1$，$F_n=...)
