【专题总结】斐波那契数列

前言

老年人的一些整理（全是网上找的）。。（复习用）

本文用\((x,y)\)表示\(gcd(x,y)\)

斐波那契数列是真的神奇啊QAQ

斐波那契数列的定义

\[ fib_{n}=\left\{ \begin{aligned} &0 & & n=0 \\ &1 & & n=1 \\ &fib_{n-1}+fib_{n-2} & & n>1 \end{aligned} \right. \]

快速求\(f_n\)

1.矩阵快速幂

\(\left[ \begin{matrix} fib_{n+1} \\ fib_{n} \end{matrix} \right]\) \(=\) \({\left[ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right]}^{n}\) \(\left[ \begin{matrix} fib_{1} \\ fib_{0} \end{matrix} \right]\)

2.通项公式（怎么求就先不写了吧。。）

\(fib_{n}\) \(=\) \(\frac{\displaystyle 1}{\displaystyle \sqrt[]{5}}\displaystyle [ {(\frac{1+\sqrt[]{5}}{2})}^{n}-{(\frac{1-\sqrt[]{5}}{2})}^{n}]\)

ps.这个通项公式看起来没用，但如果要求\(f_n\)对一个数取模，并且5在模数下有二次方根，用通项公式会有奇效。。

一些性质

斐波那契和gcd

1.\((fib_{n},fib_{n-1})=1\)

  证明：\((fib_{n},fib_{n-1})=(fib_{n-1}+fib_{n-2},fib_{n-1})=(fib_{n-1},fib_{n-2})=......\)

2.\(fib_{n+m}=fib_{n-1}fib_{m}+fib_{n}fib_{m+1}\)

  证明：令\(m=1\)和\(m=2\)直接计算成立。。。

       然后假设\(m=k-1\)和\(m=k\)都成立时，证明\(m=k+1\)时也成立

       \(fib_{n+k+1}=fib_{n+k}+fib_{n+k-1}\)

       \(fib_{n+k+1}=(fib_{n-1}fib_{k-1}+fib_{n}fib_{k})+(fib_{n-1}fib_{k}+fib_{n}fib_{k+1})\)

       \(fib_{n+k+1}=fib_{n-1}fib_{k+1}+fib_{n}fib_{k+2}\)

3.\((fib_{n+m},fib_{n})=(fib_{m},fib_{n})\)

  证明：\((fib_{n+m},fib_{n})=(fib_{n-1}fib_{m}+fib_{n}fib_{m+1},fib_{n})\)

       \((fib_{n+m},fib_{n})=(fib_{n-1}fib_{m},fib_{n})\)

       \((fib_{n+m},fib_{n})=(fib_{m},fib_{n})\)

4.\((fib_{n},fib_{m})=fib_{(n,m)}\)

  证明：套用c的结论辗转相除即可。

5.\(fib_{n}|fib_{m}\)等价于\(n|m\)

  证明：\(a|b\)等价于\((a,b)=a\),\(fib_{n}|fib_{m}\)等价于\(fib_{n}=(fib_{n},fib_{m})\)

       相当于\(fib_{n}=fib_{(n,m)}\)，于是\(n=(n,m)\)

6.每\(n\)个连续的斐波那契数有且仅有一个被\(fib_{n}\)整除

  证明：由e的结论，所有能被\(fib_{n}\)整除的\(fib_{m}\)的条件是\(n|m\)，结论就比较显然了。

斐波那契的一些恒等式（证明略。。基本都能用数学归纳法）

1.\(\displaystyle \sum_{i=0}^{n}{fib_{i}}=fib_{n+2}-1\)

2.\(fib_{1}+fib_{3}+....+fib_{2n-1}=fib_{2n}\)

3.\(fib_{2}+fib_{4}+....+fib_{2n}=fib_{2n+1}-1\)

4.\(\displaystyle \sum_{i=0}^{n}{{fib_{i}}^{2}}=fib_{n}fib_{n+1}\)

5.\(\displaystyle \sum_{i=0}^{n}{(i \cdot fib_{i})}=n \cdot fib_{n+2} - fib_{n+3} + 2\)