第1章 绪论

  斐波那契数列为F0=0F_0=0，F1=1F_1=1，Fn=Fn−1+Fn−2(n≥2)F_n=F_{n-1}+F_{n-2}(n\geq 2)，现通过6种不同的方法求它的通项公式。

第2章 特征方程法

  对于F0=0F_0=0，F1=1F_1=1，Fn=Fn−1+Fn−2(n≥2)F_n=F_{n-1}+F_{n-2}(n\geq 2)，假设解FnF_n的基本形式。

  ①常数，Fn=CF_n=C。C=C+C⇒C=0C=C+C\Rightarrow C=0，不符。

  ②一次函数，Fn=rn+sF_n=rn+s，rn+s=r(n−1)+s+r(n−2)+s⇒n=3−srrn+s=r(n-1)+s+r(n-2)+s\Rightarrow n=3-\frac{s}{r}，不符。

  ③三角函数，Fn=sin(n)F_n=sin(n)。sin(n)=sin(n−1)+sin(n−2)sin(n)=sin(n-1)+sin(n-2)，不符。

  ④对数函数，Fn=ln(n)F_n=ln(n)。ln(n)=ln(n−1)+ln(n−2)ln(n)=ln(n-1)+ln(n-2)，不符。

  ⑤指数函数，Fn=rnF_n=r^n。rn=rn−1+rn−2⇒r2=r+1⇒r2−r−1=0r^n=r^{n-1}+r^{n-2}\Rightarrow r^2=r+1\Rightarrow r^2-r-1=0，可能满足。

  故猜测Fn=rnF_n=r^n，并且rr满足r2−r−1=0r^2-r-1=0。

  rr有两个解，r1=1+52r_1=\frac{1+\sqrt{5}}{2}，r2=1−52r_2=\frac{1-\sqrt{5}}{2}。

  FnF_n通解即为两个线性无关解的组合。

Fn=Ar1n+Br2nF_n=Ar_1^n+Br_2^n

  当n=0n=0时，F0=A+B=0⇒B=−AF_0=A+B=0\Rightarrow B=-A。

  当n=1n=1时，F1=Ar1+Br2=1F_1=Ar_1+Br_2=1，带入B=−AB=-A，得

A(r1−r2)=1⇒A=15⇒B=−15A(r_1-r_2)=1\Rightarrow A=\frac{1}{\sqrt{5}}\Rightarrow B=-\frac{1}{\sqrt{5}}

  代入Fn=Ar1n+Br2nF_n=Ar_1^n+Br_2^n得，

Fn=15[(1+52)n−(1−52)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=0n=0和n=1n=1验证，满足条件。

第3章 生成函数法

  对于F0=0F_0=0，F1=1F_1=1，Fn=Fn−1+Fn−2(n≥2)F_n=F_{n-1}+F_{n-2}(n\geq 2)，定义

F(x)=∑n=0∞Fnxn=F0+F1x+F2x2+F3x3+...F(x)=\sum_{n=0}^{\infty}F_nx^n=F_0+F_1x+F_2x^2+F_3x^3+...

  等式两边同时乘xx，x2x^2，并于原式比较，

F(x)=F0+F1x+F2x2+F3x3+...x⋅F(x)=F0x+F1x2+F2x3+F3x4+...x2⋅F(x)=F0x2+F1x3+F2x4+F3x5+...\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}

  故有，

(1−x−x2)F(x)=F0+F1x−F0x+∑n=2∞(Fn−Fn−1−Fn−2)xn=F0+F1x−F0x=x\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)=x1−x−x2F(x)=\frac{x}{1-x-x^2}

  尝试将分母1−x−x21-x-x^2因式分解，令

1−x−x2=01-x-x^2=0

  解得，

x1=−1+52，x2=−1−52x_1=\frac{-1+\sqrt{5}}{2}，x_2=\frac{-1-\sqrt{5}}{2}

  故有，

1−x−x2=−(x−−1+52)⋅(x−−1−52)=−(−1+52⋅−1−52)(x⋅2−1+5−−1+52⋅2−1+5)⋅(x⋅2−1−5−−1−52⋅2−1−5)=(1+52x−1)⋅(1−52x−1)=(1−1+52x)⋅(1−1−52x)\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)=x1−x−x2=A1−1+52x+B1−1−52xF(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}

  通分得，

F(x)=A(1−1−52x)+B(1−1+52x)1−x−x2=(A+B)−(A⋅1−52+B⋅1+52)x1−x−x2=x1−x−x2\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=15=−BA=\frac{1}{\sqrt{5}}=-B。

  故有，

F(x)=15[11−1+52x−11−1−52x]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]

  由几何级数

11−ax=∑n=0∞anxn\frac{1}{1-ax}=\sum_{n=0}^{\infty}a^nx^n

  得

F(x)=15∑n=0∞[(1+52)n−(1−52)n]xnF(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)=∑n=0∞FnxnF(x)=\sum_{n=0}^{\infty}F_nx^n比较系数，得

Fn=15[(1+52)n−(1−52)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章 矩阵法

  对于F0=0F_0=0，F1=1F_1=1，Fn=Fn−1+Fn−2(n≥2)F_n=F_{n-1}+F_{n-2}(n\geq 2)，有

Fn=1⋅Fn−1+1⋅Fn2Fn−1=1⋅Fn−1+0⋅Fn2\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}

  写成矩阵，

(FnFn−1)=(1110)(Fn−1Fn−2)\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=(1110)M= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}

  故有

(FnFn−1)=M(Fn−1Fn−2)=M2(Fn−2Fn−3)=...=Mn−1(F1F0)\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}

  代入F0=0F_0=0，F1=1F_1=1，

(FnFn−1)=Mn−1(10)\begin{aligned} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = M^{n-1} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \end{aligned}

  不难发现，只需要求出Mn−1M^{n-1}即可求出FnF_n。

  计算M=(1110)M= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}的特征值与特征向量，

λ1=1+52，λ2=1−52\lambda_1=\frac{1+\sqrt{5}}{2}，\lambda_2=\frac{1-\sqrt{5}}{2}

φ1=(λ11)，φ2=(λ21)\begin{aligned} \varphi_1= \begin{pmatrix} \lambda_1 \\ 1 \end{pmatrix} ， \varphi_2= \begin{pmatrix} \lambda_2 \\ 1 \end{pmatrix} \end{aligned}

  对角化矩阵MM,

M=PDP−1M=PDP^{-1}

  其中，

P=(φ1φ2)=(λ1λ211)\begin{aligned} P= \begin{pmatrix} \varphi_1 & \varphi_2 \end{pmatrix} = \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix} \end{aligned}

D=(λ100λ2)\begin{aligned} D= \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix} \end{aligned}

P−1=15(1−λ2−1λ1)\begin{aligned} P^{-1}=\frac{1}{\sqrt{5}} \begin{pmatrix} 1 & -\lambda_2 \\ -1 & \lambda_1 \end{pmatrix} \end{aligned}

  由对角化的性质，可得

Mn−1=PDn−1P−1=15(λ1λ211)(λ1n−100λ2n−1)(1−λ2−1λ1)=15(λ1nλ2nλ1n−1λ2n−1)(1−λ2−1λ1)\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}

  故有

(FnFn−1)=Mn−1(10)=15(λ1nλ2nλ1n−1λ2n−1)(1−λ2−1λ1)(10)=15(λ1nλ2nλ1n−1λ2n−1)(1−1)=15(λ1n−λ2nλ1n−1−λ2n−1)\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}

  只看第一行，可得

Fn=15(λ1n−λ2n)F_n=\frac{1}{\sqrt{5}}(\lambda_1^n-\lambda_2^n)

  即

Fn=15[(1+52)n−(1−52)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章 移位算子法

  对于F0=0F_0=0，F1=1F_1=1，Fn=Fn−1+Fn−2(n≥2)F_n=F_{n-1}+F_{n-2}(n\geq 2)，定义移位算子EE

EFn=Fn+1EF_n=F_{n+1}

  故有

E2Fn=EFn+1=Fn+2E^2F_n=EF_{n+1}=F_{n+2}

  同理可得，

EkFn=Fn+kE^kF_n=F_{n+k}

  同时，也可以看出

Fn=EnF0=EnF_n=E^nF_0=E^n

  由Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2}得

Fn=EFn+E2Fn⇒(E2+E−1)Fn=0F_n=EF_n+E^2F_n\Rightarrow(E^2+E-1)F_n=0

  由于FnF_n不恒为00，故有

E2+E−1=0E^2+E-1=0

  解方程，得

E1=1+52，E2=1−52E_1=\frac{1+\sqrt{5}}{2}，E_2=\frac{1-\sqrt{5}}{2}

  对于特解E1E_1，我们有Fn=E1nF_n=E_1^n。对于特解E2E_2，我们有Fn=E2nF_n=E_2^n。

  故EE得通解应为

En=AE1n+BE2nE^n=AE_1^n+BE_2^n

  当n=0n=0时，F0=E0=A+B=0F_0=E^0=A+B=0。

  当n=1n=1时，F1=E1=AE1+BE2F_1=E^1=AE_1+BE_2。

  可得，A=15=−BA=\frac{1}{\sqrt{5}}=-B

  故有

Fn=En=15[(1+52)n−(1−52)n]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章 构造等比数列法

  对于F0=0F_0=0，F1=1F_1=1，Fn=Fn−1+Fn−2(n≥2)F_n=F_{n-1}+F_{n-2}(n\geq 2)，假设可以凑出以下形式

Fn−pFn−1=q(Fn−1−pFn−2)F_n-pF_{n-1}=q(F_{n-1}-pF_{n-2})

  并且令

Gn=Fn−pFn−1G_n=F_n-pF_{n-1}

  故有

Gn=qGn−1G_n=qG_{n-1}

  这是一个首项G0=1G_0=1，公比为qq的等比数列。可以求得

Gn=qn−1G_n=q^{n-1}

  将凑的式子Fn−pFn−1=q(Fn−1−pFn−2)F_n-pF_{n-1}=q(F_{n-1}-pF_{n-2})化简，得

Fn=(p+q)Fn−1−pqFn−2F_n=(p+q)F_{n-1}-pqF_{n-2}

  与Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2}对比系数，得

{p+q=1pq=−1\begin{aligned} \begin{cases} p + q&=1\\ \quad pq&=-1 \end{cases} \end{aligned}

  解得

{p=1+52q=1−52或{p=1−52q=1+52\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}

  令

{s1=1+52s2=1−52\begin{aligned} \begin{cases} s_1=\frac{1+\sqrt{5}}{2}\\ s_2=\frac{1-\sqrt{5}}{2} \end{cases} \end{aligned}

  故

{p=s1q=s2或{p=s2q=s1\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=s1，q=s2p=s_1，q=s_2时，有Gn=Fn−pFn−1=qn−1G_n=F_n-pF_{n-1}=q^{n-1}，即Fn−s1Fn−1=s2n−1①F_n-s_1F_{n-1}=s_2^{n-1}①。

  当p=s2，q=s1p=s_2，q=s_1时，有Gn=Fn−pFn−1=qn−1G_n=F_n-pF_{n-1}=q^{n-1}，即Fn−s2Fn−1=s1n−1②F_n-s_2F_{n-1}=s_1^{n-1}②。

  ①⋅s2−②⋅s1①\cdot s_2-②\cdot s_1得，(s2−s1)=Fn=s2n−s1n(s_2-s_1)=F_n=s_2^n-s_1^n，即

Fn=s2n−s1ns2−s1F_n=\frac{s_2^n-s_1^n}{s_2-s_1}

  代入s1s_1和s2s_2得

Fn=15[(1+52)n−(1−52)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]

第7章 无穷连分数法

  对于F0=0F_0=0，F1=1F_1=1，Fn=Fn−1+Fn−2(n≥2)F_n=F_{n-1}+F_{n-2}(n\geq 2)，我们对Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2}等式两边同时除以Fn−1F_{n-1}，得

FnFn−1=1+Fn−2Fn−1\frac{F_n}{F_{n-1}}=1+\frac{F_{n-2}}{F_{n-1}}

  令

xn=FnFn−1x_n=\frac{F_n}{F_{n-1}}

  故有

xn=1+1xn−1x_n=1+\frac{1}{x_{n-1}}

  将上式一直迭代，得

xn=1+1xn−1=1+11+1xn−2=1+11+11+1xn−3=...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}}}}=...

  取极限

φ=lim⁡n→∞xn=1+11+11+1⋱\varphi=\lim_{n\rightarrow\infty}x_n=1+\frac{1}{1+\frac{1}{1+\frac{1}{\ddots}}}

  故有

φ=1+1φ\varphi=1+\frac{1}{\varphi}

  取φ>0\varphi>0解得

φ=1+52\varphi=\frac{1+\sqrt{5}}{2}

  现在证

φn=φFn+Fn−1\varphi^n=\varphi F_n+F_{n-1}

  成立，用归纳法。

  由φ=1+1φ\varphi=1+\frac{1}{\varphi}得，

φ2=φ+1\varphi^2=\varphi+1

  当n=1n=1时，有φ1=φF1+F0\varphi^1=\varphi F_1+F_0成立；

  当n=kn=k且φk−1=φFk−1+Fk−2\varphi^{k-1}=\varphi F_{k-1}+F_{k-2}时，

φk−1=φFk−1+Fk−2⇒φk=φ2Fk−1+φFk−2⇒φk=(φ+1)Fk−1+φFk−2⇒φk=φ(Fk−1+Fk−2)+Fk−1⇒φk=φFk+Fk−1\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}

  综上，

φn=φFn+Fn−1\varphi^n=\varphi F_n+F_{n-1}

  成立。

  即

Fn=φn−1−φ−1Fn−1F_n=\varphi^{n-1}-\varphi^{-1}F_{n-1}

  继续迭代

Fn=φn−1−φ−1(φn−2−φ−2Fn−2)=φn−1−φn−3+φ−3Fn−2=φn−1−φn−3+φn−5−φ−5Fn−3=φn−1−φn−3+φn−5−φn−7+φ−7Fn−4=φn−1−φn−3+φn−5−...−(−1)nφ−n+1+(−1)nφ−2n+1F0=φn−1−φn−3+φn−5−...−(−1)nφ−n+1=φn−1[1−(−φ−2)n]1+φ−2=φn−1−(−1)nφ−n−11+φ−2=φ−11+φ−2[φn−(−1φ)n]\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}

  代入φ=1+52\varphi=\frac{1+\sqrt{5}}{2}，得

Fn=15[(1+52)n−(1−52)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]

许可协议

本文由Primerusse编写

分享文章