大部分是上课做的笔记，包含我自己的一些思考的推导，希望可以帮助到大家！
本文在以下平台同步发送：洛谷（已通过全站推荐）、博客园。
（因为洛谷专栏更新需要重新审核全站推荐，所以更新相对博客园略有延迟）
UPD 2024.11.2：撤除了引用格式并添加了分割线以分割不同结论及证明；修正了整除的 \KaTeX 格式；增加了某些括号和分数的大小以增强可读性。
-
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 |
... |
n-1 |
n |
n+1 |
... |
n+k-1 |
n+k |
... |
| 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
连续使用更相减损术即可
\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 \mid 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+2}-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=\dfrac{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 \dfrac{fib_{n+2}+fib_{n-2}}{3}=\dfrac{3fib_n}{3}=fib_n
-
\dfrac{fib_i}{fib_{i-1}}=\dfrac{\sqrt{5}+1}{2} \approx 1.618
-
\dfrac{fib_i}{fib_{i+1}}=\dfrac{\sqrt{5}-1}{2} \approx 0.618
-
fib_n=\dfrac{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}