大部分是上课做的笔记，包含我自己的一些思考的推导，希望可以帮助到大家！
（更好的阅读体验）洛谷专栏查看：点击此处
- \(fib_{n+k}=fib_n \times fib_{k+1}+fib_{n-1} \times fib_{k}\)
经典模型：一段台阶有 \(n\) 阶，从第 \(\mathbf{1}\) 阶开始，每次可以向上跳 \(1\) 阶或 \(2\) 阶，跳到第 \(n\) 阶的方案数即为 \(fib_n\)，跳到每一阶的方案数为斐波那契数列。
1 2 3 ... n-1 n n+1 ... n+k-1 n+k n+k+1 ... 1 2 ... k k+1 1 ... k-1 k 从 \(1\) 到 \(n+k\) 分为经过 \(n\) 和不经过 \(n\) 两种路线。设从 \(l\) 到 \(r\) 的路线数量为 \(cnt_{l,r}\)，则根据模型结论，\(cnt_{1,n}=fib_n\)。
- 经过 \(n\) 的路线数量 \(=cnt_{1,n} \times cnt_{n,k}\)，把 \(n\) 看作 \(1\) 后，\(n+k\) 被看作 \(k+1\)（见上表第二行），所以 \(cnt_{n,k}= fib_{k+1}\)。总数为 \(fib_n \times fib_{k+1}\)；
- 不经过 \(n\) 的路线数量 \(= cnt_{1,n-1} \times cnt_{n-1,n+1} \times cnt_{n+1,n+k}\)。由于不能经过 \(n\)，所以 \(cnt_{n-1,n+1}\) 有且仅有跳 \(2\) 阶一种方案，故 \(cnt_{n-1,n+1}=1\)；把 \(n+1\) 看作 \(1\) 后，\(n+k\) 被看作 \(k\)（见上表第三行），所以 \(cnt_{n+1,n+k}=fib_k\)。总数为 \(fib_{n-1} \times 1 \times fib_k = fib_{n-1} \times fib_k\)。
综上所述，\(fib_{n+k}=\) 经过 \(n\) 的路线数量 \(+\) 不经过 \(n\) 的路线数量 \(=fib_n \times fib_{k+1} + fib_{n-1} \times fib_k\)
- \(\gcd(fib_n,fib_{n-1})=1\)
连续使用更相减损术即可
\( \begin{aligned} &\gcd(fib_{k+1},fib_k)\\ =&\gcd(fib_k,fib_{k+1}-fib_k)\\ =&\gcd(fib_k,fib_{k-1})\\ =&\gcd(fib_{k-1},fib_{k-2})\\ =&\dots\\ =&\gcd(fib_2,fib_1)\\ =&\gcd(1,1)\\ =&1 \end{aligned} \)
- \(\gcd(fib_n,fib_m)=fib_{\gcd(n,m)}\)
设 \(k=m-n, m=n+k\)
\(fib_m=fib_{n+k}=fib_n \times fib_{k+1}+fib_{n-1} \times fib_{k}\)
\(\gcd(fib_n,fib_m)=\gcd(fib_n,fib_n \times fib_{k+1}+fib_{n-1} \times fib_{k})\)
\(\because fib_n | fib_n \times fib_{k+1}\)
\( \begin{aligned} \therefore \quad &\gcd(fib_n,fib_n \times fib_{k+1}+fib_{n-1} \times fib_{k})\\ =&\gcd(fib_n,fib_{n-1} \times fib_{k})\\ =&\gcd(fib_n,fib_{n-m}) \end{aligned} \)
观察到 \(\gcd(fib_n,fib_m)=\gcd(fib_n,fib_{n-m})\) 与更相减损术中的 \(\gcd(n,m)=\gcd(n,n-m)\) 相似，所以将两者同时执行类似更相减损术的操作，过程中的 \(n,m\) 值始终相等。
所以 \(\gcd(fib_n,fib_m)=fib_{\gcd(n,m)}\)
- \(\sum_{i=1}^{n}fib_i=fib_{n+1}-1\)
在等号左边补上一个 \(fib_2\) 后可以连续合并，最后再减去 \(fib_2=1\)。
\( \begin{aligned} \quad &\sum_{i=1}^{n}fib_i\\ =&fib_1+fib_2+fib_3+\dots+fib_{n-1}+fib_n\\ =&(fib_1+fib_2+fib_2+fib_3+\dots+fib_{n-1}+fib_n)-fib_2\\ =&(fib_2+fib_3+fib_3+fib_4+\dots+fib_{n-1}+fib_n)-fib_2\\ =&(fib_3+fib_4+fib_4+fib_5+\dots+fib_{n-1}+fib_n)-fib_2\\ =&\dots\\ =&(fib_{n-2}+fib_{n-1}+fib_{n-1}+fib{n})-fib_2\\ =&(fib_{n-1}+fib_n+fib_n)-fib_2\\ =&(fib_n+fib_{n+1})-fib_2\\ =&fib_{n+2}-fib_2\\ =&fib_{n+2}-1 \end{aligned} \)
- \(\sum_{i=1}^{n}fib_{2i-1}=fib_{2n}\)
将 \(fib_{2n}\) 直接拆开即可。
\( \begin{aligned} \quad &fib_{2n}\\ =&fib_{2n-1}+fib_{2n-2}\\ =&fib_{2n-1}+fib_{2n-3}+fib_{2n-4}\\ =&fib_{2n-1}+fib_{2n-3}+fib_{2n-5}+fib_{2n-6}\\ =&\dots\\ =&fib_{2n-1}+fib_{2n-3}+\dots+fib_1\\ =&\sum_{i=1}^{n}fib_{2i-1}=fib_{2n} \end{aligned} \)
- \(\sum_{i=1}^{n}fib_i^2=fib_n \times fib_{n+1}\)
将斐波那契数列转换成上图，每一项对应一个正方形的边长
总面积为 \(\sum_{i=1}^{n}fib_i^2\)，短边长为 \(fib_n\)，长边长为 \(fib_{n+1}\)
所以 \(\sum_{i=1}^{n}fib_i^2=fib_n \times fib_{n+1}\)
- \(fib_n^2=fib_{n-1} \times fib_{n+1} + (-1)^{n-1}\)
暂时证明不来，可以从面积的方面考虑，大佬也可尝试数学归纳法
- \(fib_n=\frac{fib_{n+2}+fib_{n-2}}{3}\)
\( \begin{aligned} \quad &fib_{n+2}+fib_{n-2}\\ =&fib_{n+1}+fib_n+fib_{n-2}\\ =&fib_{n}+fib_{n-1}+fib_n+fib_{n-2}\\ =&2fib_n+fib_{n-1}+fib_{n-2}\\ =&3fib_n \end{aligned} \)
\(\therefore \frac{fib_{n+2}+fib_{n-2}}{3}=\frac{3fib_n}{3}=fib_n\)
-
\(\frac{fib_i}{fib_{i-1}}=\frac{\sqrt{5}+1}{2} \approx 1.618\)
-
\(\frac{fib_i}{fib_{i+1}}=\frac{\sqrt{5}-1}{2} \approx 0.618\)
- \[fib_n=\frac{(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}} \]