斐波那契数列详解

2021-10-28

Fibnacci

1.基本的递推性质:

  1. \(f_n=f_{n-1}+f_{n-2}\)
  2. \(\sum\limits_{i=1}^{n}f_i=f_{n+2}-1\)
  3. \(\sum\limits_{i=1}^{n}f^2_i=f_n\times f_{n+1}\)
  4. \(f_1+f_3+f_5+...+f_{2n-1}=f_{2n}\)
  5. \(f_2+f_4+f_6+...+f_{2n}=f_{2n+1}-1\)
  6. \(f_n=f_m\times f_{n-m+1}+f_{m-1}\times f_{n-m}(n\geq m)\)
  7. \(f_{n-1}\times f_{n+1}=f_n^2+(-1)^n\)
  8. \(\frac{f_{2n}}{f_n}=f_{n-1}+f_{n+1}\)
  9. 一般用不到:\(f_{2n-2m-2}(f_{2n}+f_{2n+2})=f_{2m+2}+f_{4n-2m}(n>m\geq-1,n\geq-1)\)

证明:

  1. 显然

  2. \(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}\)

    上式相加消去相同元素,得证

  3. 可使用上面2的证明方式得出,不再给出证明

  4. 同2

  5. 同2

  6. \(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}...\)

    不难发现系数仍然是斐波那契数列,那么整理可得证

  7. (不会)

2.与集合的关系

\(f_{n+2}\)项是集合\(\textit{1,2,...,n}\)中所有不包含相邻正整数子集的个数

3.与杨辉三角(组合数学)的关系

image

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}\)

参考资料

度娘

大佬博客