斐波那契数列详解
Fibnacci
1.基本的递推性质：
- \(f_n=f_{n-1}+f_{n-2}\)
- \(\sum\limits_{i=1}^{n}f_i=f_{n+2}-1\)
- \(\sum\limits_{i=1}^{n}f^2_i=f_n\times f_{n+1}\)
- \(f_1+f_3+f_5+…+f_{2n-1}=f_{2n}\)
- \(f_2+f_4+f_6+…+f_{2n}=f_{2n+1}-1\)
- \(f_n=f_m\times f_{n-m+1}+f_{m-1}\times f_{n-m}(n\geq m)\)
- \(f_{n-1}\times f_{n+1}=f_n^2+(-1)^n\)
- \(\frac{f_{2n}}{f_n}=f_{n-1}+f_{n+1}\)
- 一般用不到：\(f_{2n-2m-2}(f_{2n}+f_{2n+2})=f_{2m+2}+f_{4n-2m}(n>m\geq-1,n\geq-1)\)
证明：
-
显然 -
\(f_1=f_3-f_1\)
\(f_2=f_4-f_3\)
\(f_3=f_5-f_4…\)
\(f_n=f_{n+2}-f_{n+1}\)
上式相加消去相同元素，得证
-
可使用上面2的证明方式得出，不再给出证明
-
同2
-
同2
-
\(f_n=f_{n-1}+f_{n-2}\)
\(f_n=2f_{n-2}+f_{n-3}\)
\(f_n=3f_{n-3}+2f_{n-4}\)
\(f_n=5f_{n-4}+3f_{n-5}…\)
不难发现系数仍然是斐波那契数列，那么整理可得证
-
（不会）
2.与集合的关系
第\(f_{n+2}\)项是集合\(\textit{1,2,…,n}\)中所有不包含相邻正整数子集的个数
3.与杨辉三角（组合数学）的关系
4.通项公式
\(f_n=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n]\)
看到里面的一个数跟黄金分割非常像，他确实也跟黄金分割有很大关系，不过过一会再提，先看证明
假设有\(a,b\)使
\(f_n-af_{n-1}=b(f_{n-1}-af_{n-2})\\
f_n=(a+b)f_{n-1}-abf_{n-1}\)
有
\(\left\{\begin{matrix}
a+b=1 \\ ab=1
\end{matrix}\right.\)
解得
\(\left\{\begin{matrix}
a=\frac{1+\sqrt{5}}{2}\\
b=\frac{1-\sqrt{5}}{2}
\end{matrix}\right.
or
\left\{\begin{matrix}
a=\frac{1-\sqrt{5}}{2}\\
b=\frac{1+\sqrt{5}}{2}
\end{matrix}\right.\)
\(f_n-af_{n-1}=b(f_{n-1}-af_{n-2})\)
\(\frac{f_n-af_{n-1}}{f_{n-1}-af_{n-2}}=b\)
令\(S_{n}=f_n-af_{n-1}\),则
\(\left\{\begin{matrix}
\frac{S_n}{S_{n-1}}=b\\
S_1=f_1-af_0=1
\end{matrix}\right.\)
进而可得\(S_n=b^{n-1}\Rightarrow f_n-af_{n-1}=b^{n-1}\)
那么\(f_n=b^{n-1}+af_{n-1}\)，把求得的\(a,b\)代入得
\(\left\{\begin{matrix}
f_n=(\frac{1-\sqrt{5}}{2})^{n-1}+\frac{1+\sqrt{5}}{2}f_{n-1}\\
f_n=(\frac{1+\sqrt{5}}{2})^{n-1}+\frac{1-\sqrt{5}}{2}f_{n-1}
\end{matrix}\right.\)
\((\frac{1+\sqrt{5}}{2})^{n-1}+\frac{1-\sqrt{5}}{2}f_{n-1}=(\frac{1-\sqrt{5}}{2})^{n-1}+\frac{1+\sqrt{5}}{2}f_{n-1}\)
\(\left [(\frac{1+\sqrt{5}}{2})^{n-1}-(\frac{1-\sqrt{5}}{2})^{n-1} \right ]=\sqrt{5}f_{n-1}\)
\(f_{n-1}=\left [(\frac{1+\sqrt{5}}{2})^{n-1}-(\frac{1-\sqrt{5}}{2})^{n-1} \right ]\frac{1}{\sqrt{5}}\)
\(f_{n}=\left [(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n} \right ]\frac{1}{\sqrt{5}}\)
\(\square\)
5.黄金分割的关系
关于相邻两项的比值，在\(n\)趋于无限时等于黄金分割比，即
\(\lim\limits_{n\to \infty}\frac{f_n}{f_{n+1}}=\frac{\sqrt{5}-1}{2}\)
6.不太重要的公式
当时在做斐波这道题的时候考场上自己推出来了一个式子，应该是对的，但是翻遍了博客没有看到一样的
不知道能不能用前\(n\)项平方和公式证明，在这里给一下吧
\(f_n^2+f_{n+1}^2=f_{2n+1}\)
参考资料
