Fibonacci 数列

设f(x)=1,x∈{1,2}=f(x−1)+f(x−2),x∈[3,∞)\begin{aligned}f(x)&=1,\quad\quad\quad\quad\quad\quad\quad\quad\quad x\in\{1,2\}\\
&=f(x-1)+f(x-2),\quad x\in[3,∞)
\end{aligned}f(x)​=1,x∈{1,2}=f(x−1)+f(x−2),x∈[3,∞)​

则 f(x)f(x)f(x) 的通项公式为f(x)=15[(1+52)x−(1−52)x]f(x)=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^x-(\frac{1-\sqrt{5}}{2})^x]f(x)=5​1​[(21+5​​)x−(21−5​​)x]

证明： 采用数学归纳法完成证明。

当 x=1x=1x=1 或 222 时，结论显然成立。

设 x=n−1x=n-1x=n−1 或 x=nx=nx=n 时结论成立。根据定义式，有

f(n+1)=f(n)+f(n−1)=15[(1+52)n−(1−52)n+(1+52)n−1−(1−52)n−1]=15[(1+52)n−1(1+52+1)−(1−52)n−1(1−52+1)]\begin{aligned}f(n+1)&=f(n)+f(n-1)\\
&=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n+(\frac{1+\sqrt{5}}{2})^{n-1}-(\frac{1-\sqrt{5}}{2})^{n-1}]\\
&=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^{n-1}(\frac{1+\sqrt{5}}{2}+1)-(\frac{1-\sqrt{5}}{2})^{n-1}(\frac{1-\sqrt{5}}{2}+1)]
\end{aligned}f(n+1)​=f(n)+f(n−1)=5​1​[(21+5​​)n−(21−5​​)n+(21+5​​)n−1−(21−5​​)n−1]=5​1​[(21+5​​)n−1(21+5​​+1)−(21−5​​)n−1(21−5​​+1)]​

而(1+52)2=6+254=1+52+1(1−52)2=1−52+1\begin{aligned}(\frac{1+\sqrt5}{2})^2&=\frac{6+2\sqrt5}{4}&=\frac{1+\sqrt5}{2}+1\\
(\frac{1-\sqrt5}{2})^2&=&\frac{1-\sqrt5}{2}+1\end{aligned}(21+5​​)2(21−5​​)2​=46+25​​=​=21+5​​+121−5​​+1​

∴\therefore∴f(n+1)=15[(1+52)n−1(1+52)2−(1−52)n−1(1−52)2]=15[(1+52)n+1−(1−52)n+1].\begin{aligned}f(n+1)&=\frac{1}{\sqrt5}[(\frac{1+\sqrt{5}}{2})^{n-1}(\frac{1+\sqrt{5}}{2})^2-(\frac{1-\sqrt{5}}{2})^{n-1}(\frac{1-\sqrt{5}}{2})^2]\\
&=\frac{1}{\sqrt5}[(\frac{1+\sqrt{5}}{2})^{n+1}-(\frac{1-\sqrt{5}}{2})^{n+1}].\end{aligned}f(n+1)​=5​1​[(21+5​​)n−1(21+5​​)2−(21−5​​)n−1(21−5​​)2]=5​1​[(21+5​​)n+1−(21−5​​)n+1].​

所以，对于 ∀x∈Z∗\forall x\in\Z^*∀x∈Z∗，原式都成立。Q.E.D..\text{Q.E.D..}Q.E.D..

Fibonacci 数列的性质

1. gcd⁡(f(i),f(j))=f(gcd⁡(i,j)).\gcd(f(i),f(j))=f(\gcd(i,j)).gcd(f(i),f(j))=f(gcd(i,j)).
   
   证明： 详见素数与 Miller-Rabin 测试。
2. 若非负整数 n ∣ mn\ |\ mn ∣ m，则 f(n) ∣ f(m).f(n)\ |\ f(m).f(n) ∣ f(m).
   
   证明： 由 性质1 得 gcd⁡(f(n),f(m))=f(gcd⁡(n,m)),\gcd(f(n),f(m))=f(\gcd(n,m)),gcd(f(n),f(m))=f(gcd(n,m)),
   
   而 n ∣ mn\ |\ mn ∣ m， ∴n=gcd⁡(n,m). Q.E.D..\therefore n=\gcd(n,m).\text{ Q.E.D..}∴n=gcd(n,m). Q.E.D..
3. 若 n∈Z∗n\in\Z^*n∈Z∗，则 ∑i=1nf(i)=f(n+2)−1\sum_{i=1}^{n}{f(i)}=f(n+2)-1i=1∑n​f(i)=f(n+2)−1
   
   证明： 采用数学归纳法完成证明。
   
   当 n=1n=1n=1 时，结论显然成立。
   
   设 n=kn=kn=k 时结论成立。则
   
   ∑i=1k+1f(i)=∑i=1kf(i)+f(k+1)=f(k+2)−1+f(k+1)=f(k+3)−1\begin{aligned}\sum_{i=1}^{k+1}{f(i)}&=\sum_{i=1}^{k}{f(i)+f(k+1)}\\
   &=f(k+2)-1+f(k+1)\\
   &=f(k+3)-1\end{aligned}i=1∑k+1​f(i)​=i=1∑k​f(i)+f(k+1)=f(k+2)−1+f(k+1)=f(k+3)−1​
   
   所以，对于 ∀n∈Z∗\forall n\in\Z^*∀n∈Z∗，原式都成立。Q.E.D..\text{Q.E.D..}Q.E.D..

Fibonacci 数列的推论

1. 在取模的意义下，Fibonacci 数列会出现循环。
   
   证明： 略。
2. (1) 奇数项求和。设 n∈Z∗n\in\Z^*n∈Z∗，则 ∑i=1nf(2i−1)=f(2n)−f(2)+f(1)\sum_{i=1}^{n}{f(2i-1)}=f(2n)-f(2)+f(1)i=1∑n​f(2i−1)=f(2n)−f(2)+f(1)
   
   证明： 采用数学归纳法完成证明。
   
   当 n=1n=1n=1 时，结论显然成立。
   
   设 n=kn=kn=k 时结论成立，则∑i=1k+1f(2i−1)=[∑i=1kf(2i−1)]+f(2k+1)=f(2k)+f(2k+1)−f(2)+f(1)=f(2(k+1))−f(2)+f(1).\begin{aligned}\sum_{i=1}^{k+1}{f(2i-1)}&=[\sum_{i=1}^{k}{f(2i-1)}]+f(2k+1)\\
   &=f(2k)+f(2k+1)-f(2)+f(1)\\
   &=f(2(k+1))-f(2)+f(1).\end{aligned}i=1∑k+1​f(2i−1)​=[i=1∑k​f(2i−1)]+f(2k+1)=f(2k)+f(2k+1)−f(2)+f(1)=f(2(k+1))−f(2)+f(1).​
   
   所以，对于 ∀n∈Z∗\forall n\in\Z^*∀n∈Z∗，原式都成立。Q.E.D..\text{Q.E.D..}Q.E.D..
   
   后面几条推论的证明，原理与此条类似，请读者自行证明。
   
   (2) 偶数项求和。设 n∈Z∗n\in\Z^*n∈Z∗，则 ∑i=1nf(2i)=f(2n+1)−f(1)\sum_{i=1}^{n}{f(2i)}=f(2n+1)-f(1)i=1∑n​f(2i)=f(2n+1)−f(1)
   
   证明： 采用数学归纳法完成证明。
   
   当 n=1n=1n=1 时，结论显然成立。
   
   设 n=kn=kn=k 时结论成立，则
   
   ∑i=1k+1f(2i)=[∑i=1kf(2i)]+f(2k+2)=f(2k+1)+f(2k+2)−f(1)=f(2(k+1))−f(1)\begin{aligned}\sum_{i=1}^{k+1}f(2i)&=[\sum_{i=1}^{k}f(2i)]+f(2k+2)\\
   &=f(2k+1)+f(2k+2)-f(1)\\
   &=f(2(k+1))-f(1)\end{aligned}i=1∑k+1​f(2i)​=[i=1∑k​f(2i)]+f(2k+2)=f(2k+1)+f(2k+2)−f(1)=f(2(k+1))−f(1)​
   
   故结论成立。
   
   (3) 平方项求和。设 n∈Z∗n\in\Z^*n∈Z∗，则 ∑i=1nf2(i)=f(n)×f(n+1)\sum_{i=1}^{n}{f^2(i)}=f(n)\times f(n+1)i=1∑n​f2(i)=f(n)×f(n+1)
   
   证明： 采用数学归纳法完成证明。
   
   当 n=1n=1n=1 时，结论显然成立。
   
   设当 n=kn=kn=k 时结论成立，则
   
   ∑i=1k+1f2(i)=[∑i=1kf2(i)]+f2(k+1)=f(k)×f(k+1)+f2(k+1)=f(k+1)×(f(k)+f(k+1))=f(k+1)×f(k+2)\begin{aligned}\sum_{i=1}^{k+1}{f^2(i)}&=[\sum_{i=1}^{k}{f^2(i)}]+f^2(k+1)\\
   &=f(k)\times f(k+1)+f^2(k+1)\\
   &=f(k+1)\times(f(k)+f(k+1))\\
   &=f(k+1)\times f(k+2)\end{aligned}i=1∑k+1​f2(i)​=[i=1∑k​f2(i)]+f2(k+1)=f(k)×f(k+1)+f2(k+1)=f(k+1)×(f(k)+f(k+1))=f(k+1)×f(k+2)​
   
   故结论成立。

Lucas 数列

卢卡斯数列 (Lucas Sequence) 和斐波那契数列 (Fibonacci Sequence) 有莫大的关系。

设 L(1)=1,L(2)=3,L(x)=L(x−1)+L(x−2).x∈[3,∞)\begin{aligned}L(1)&=1,L(2)=3,\\
L(x)&=L(x-1)+L(x-2).\quad x\in[3,∞)
\end{aligned}L(1)L(x)​=1,L(2)=3,=L(x−1)+L(x−2).x∈[3,∞)​则 L(x)L(x)L(x) 的通项公式是 L(x)=(1+52)x+(1−52)xL(x)=(\frac{1+\sqrt5}{2})^x+(\frac{1-\sqrt5}{2})^xL(x)=(21+5​​)x+(21−5​​)x

Lucas 数列的性质

以下式中的 FFF 是 Fibonacci 数。

为记述简便，设A=1+52, B=1−52.A=\frac{1+\sqrt5}{2},\\\ \\B=\frac{1-\sqrt5}2.A=21+5​​, B=21−5​​.

1. ∀n≥2\forall n\geq2∀n≥2 有 L2(n)−L(n+1)L(n−1)=5×(−1)n.L^2(n)-L(n+1)L(n-1)=5\times(-1)^n.L2(n)−L(n+1)L(n−1)=5×(−1)n.
   
   证明： 左边=(An+Bn)2−(An+1+Bn+1)(An−1+Bn−1)=A2n+B2n+2AnBn−A2n−An+1Bn−1−An−1Bn+1−B2n=2AnBn−An+1Bn−1−An−1Bn+1=AnBn−1(B−A)+An−1Bn(A−B)=(A−B)(An−1Bn−AnBn−1)=−(A−B)2⋅An−1Bn−1\begin{aligned}左边&=(A^n+B^n)^2-(A^{n+1}+B^{n+1})(A^{n-1}+B^{n-1})\\
   &=A^{2n}+B^{2n}+2A^nB^n-A^{2n}-A^{n+1}B^{n-1}-A^{n-1}B^{n+1}-B^{2n}\\
   &=2A^nB^n-A^{n+1}B^{n-1}-A^{n-1}B^{n+1}\\
   &=A^nB^{n-1}(B-A)+A^{n-1}B^n(A-B)\\
   &=(A-B)(A^{n-1}B^n-A^nB^{n-1})\\
   &=-(A-B)^2·A^{n-1}B^{n-1}\end{aligned}左边​=(An+Bn)2−(An+1+Bn+1)(An−1+Bn−1)=A2n+B2n+2AnBn−A2n−An+1Bn−1−An−1Bn+1−B2n=2AnBn−An+1Bn−1−An−1Bn+1=AnBn−1(B−A)+An−1Bn(A−B)=(A−B)(An−1Bn−AnBn−1)=−(A−B)2⋅An−1Bn−1​
   
   而 A−B=5A-B=\sqrt5A−B=5​，且 A×B=−1.A\times B=-1.A×B=−1.
   
   ∴左边=−5×(−1)n−1=5×(−1)n=右边.\begin{aligned}\therefore左边&=-5\times(-1)^{n-1}\\
   &=5\times(-1)^n\\
   &=右边.\end{aligned}∴左边​=−5×(−1)n−1=5×(−1)n=右边.​
   
   Q.E.D..\text{Q.E.D..}Q.E.D..

2. ∀n∈Z∗\forall n\in\Z^*∀n∈Z∗ 有 ∑i=1nL2(i)=L(n)L(n+1)−2\sum_{i=1}^{n}{L^2(i)}=L(n)L(n+1)-2i=1∑n​L2(i)=L(n)L(n+1)−2
   
   证明： 因为 L2(i)=(An+Bn)2=A2n+B2n+2AnBn=A2n+B2n+2×(−1)n\begin{aligned}L^2(i)&=(A^n+B^n)^2\\
   &=A^{2n}+B^{2n}+2A^nB^n\\
   &=A^{2n}+B^{2n}+2\times(-1)^n\end{aligned}L2(i)​=(An+Bn)2=A2n+B2n+2AnBn=A2n+B2n+2×(−1)n​
   
   所以 左边=∑i=1n(A2i+B2i+2×(−1)i)=[∑i=1n(A2i+B2i)]+2×(−1)n\begin{aligned}左边&=\sum_{i=1}^{n}{(A^{2i}+B^{2i}+2\times(-1)^i)}\\
   &=[\sum_{i=1}^{n}{(A^{2i}+B^{2i})}]+2\times(-1)^n\end{aligned}左边​=i=1∑n​(A2i+B2i+2×(−1)i)=[i=1∑n​(A2i+B2i)]+2×(−1)n​
   
   而 右边=(An+Bn)(An+1+Bn+1)−2=A2n+1+AnBn+1+An+1Bn+B2n+1−2=A2n+1+B2n+1+AnBn(A+B)\begin{aligned}右边&=(A^n+B^n)(A^{n+1}+B^{n+1})-2\\
   &=A^{2n+1}+A^nB^{n+1}+A^{n+1}B^n+B^{2n+1}-2\\
   &=A^{2n+1}+B^{2n+1}+A^nB^n(A+B)\end{aligned}右边​=(An+Bn)(An+1+Bn+1)−2=A2n+1+AnBn+1+An+1Bn+B2n+1−2=A2n+1+B2n+1+AnBn(A+B)​
   
   因为 A+B=1A+B=1A+B=1
   
   由 偶数项求和 知 ∑i=1n(A2i+B2i)=A2n+1+B2n+1−(−1)n\sum_{i=1}^{n}{(A^{2i}+B^{2i})}=A^{2n+1}+B^{2n+1}-(-1)^ni=1∑n​(A2i+B2i)=A2n+1+B2n+1−(−1)n
   
   所以 右边=A2n+1+B2n+1+(−1)n=左边.右边=A^{2n+1}+B^{2n+1}+(-1)^n=左边.右边=A2n+1+B2n+1+(−1)n=左边.
   
    Q.E.D..\text{ Q.E.D..} Q.E.D..

3. ∀m,n∈Z∗\forall m,n\in\Z^*∀m,n∈Z∗ 有 L(m+n)=12×(5F(m)F(n)+L(m)L(n)).L(m+n)=\frac12\times(5F(m)F(n)+L(m)L(n)).L(m+n)=21​×(5F(m)F(n)+L(m)L(n)).
   
   证明： 2×右边=5×(15)2(Am−Bm)(An−Bn)+(Am+Bm)(An+Bn)=Am+n+Bm+n−AmBn−AnBm+Am+n+Bm+n+AmBn+AnBm=2Am+n+2Bm+n\begin{aligned}2\times右边&=5\times(\frac1{\sqrt5})^2(A^m-B^m)(A^n-B^n)+(A^m+B^m)(A^n+B^n)\\
   &=A^{m+n}+B^{m+n}-A^mB^n-A^nB^m\\&\quad+A^{m+n}+B^{m+n}+A^mB^n+A^nB^m\\
   &=2A^{m+n}+2B^{m+n}\end{aligned}2×右边​=5×(5​1​)2(Am−Bm)(An−Bn)+(Am+Bm)(An+Bn)=Am+n+Bm+n−AmBn−AnBm+Am+n+Bm+n+AmBn+AnBm=2Am+n+2Bm+n​
   
   所以 2×(左边−右边)=2Am+n+2Bm+n−(2Am+n+2Bm+n)=0\begin{aligned}2\times(左边-右边)&=2A^{m+n}+2B^{m+n}\\
   &\quad-(2A^{m+n}+2B^{m+n})\\
   &=0\end{aligned}2×(左边−右边)​=2Am+n+2Bm+n−(2Am+n+2Bm+n)=0​
   
   原命题得证。

4. ∀m,n∈Z∗,m≠n\forall m,n\in\Z^*,m\neq n∀m,n∈Z∗,m̸​=n 有 L(m−n)=12×(−1)n(L(m)L(n)−5F(m)F(n)).L(m-n)=\frac12\times(-1)^n(L(m)L(n)-5F(m)F(n)).L(m−n)=21​×(−1)n(L(m)L(n)−5F(m)F(n)).
   
   证明： 2×右边=(−1)n[(Am+Bm)(An+Bn)−(Am−Bm)(An−Bn)]=(−1)n(AmBn+2AnBm)2×(右边−左边)=(−1)n(2AmBn+2AnBm)−2Am−n−2Bm−n=2×[Am−n(±AnBn−1)+Bm−n(±AnBn−1)]=2(±AnBn−1)(Am−n+Bm−n)\begin{aligned}2\times右边&=(-1)^n[(A^m+B^m)(A^n+B^n)-(A^m-B^m)(A^n-B^n)]\\
   &=(-1)^n(A^mB^n+2A^nB^m)\\\\
   2\times(右边-左边)&=(-1)^n(2A^mB^n+2A^nB^m)-2A^{m-n}-2B^{m-n}\\
   &=2\times[A^{m-n}(±A^nB^n-1)+B^{m-n}(±A^nB^n-1)]\\
   &=2(±A^nB^n-1)(A^{m-n}+B^{m-n})\end{aligned}2×右边2×(右边−左边)​=(−1)n[(Am+Bm)(An+Bn)−(Am−Bm)(An−Bn)]=(−1)n(AmBn+2AnBm)=(−1)n(2AmBn+2AnBm)−2Am−n−2Bm−n=2×[Am−n(±AnBn−1)+Bm−n(±AnBn−1)]=2(±AnBn−1)(Am−n+Bm−n)​
   
   而 AnBn=(−1)nA^nB^n=(-1)^nAnBn=(−1)n
   
   所以 ±AnBn−1=0±A^nB^n-1=0±AnBn−1=0
   
   原命题成立。

5. ∀n∈Z∗\forall n\in\Z^*∀n∈Z∗ 有 L2(n)−5F2(n)=4×(−1)n.L^2(n)-5F^2(n)=4\times(-1)^n.L2(n)−5F2(n)=4×(−1)n.
   
   证明： 左边=(An+Bn)2−(An−Bn)2=4AnBn=4×(−1)n=右边.\begin{aligned}左边&=(A^n+B^n)^2-(A^n-B^n)^2\\
   &=4A^nB^n\\
   &=4\times(-1)^n\\
   &=右边.\end{aligned}左边​=(An+Bn)2−(An−Bn)2=4AnBn=4×(−1)n=右边.​
   
   Q.E.D..\text{Q.E.D..}Q.E.D..

总结

1. 两个 Fibonacci 数相乘，系数极有可能与 555 有关；
2. A、BA、BA、B 两个数的代数性质很重要，A+B=1,A−B=5,A×B=−1.\begin{aligned}A+B&=1,\\A-B&=\sqrt5,\\A\times B&=-1.\end{aligned}A+BA−BA×B​=1,=5​,=−1.​