请求借助楼梯问题示例证明斐波那契恒等式$F_{2n}=F_{n}^{2}+F_{n-1}^{2}$

首先，先澄清一个小细节：按照你给出的斐波那契定义（$F_{0}=0$，$F_{1}=1$，$F_{2}=1$，$F_{n}=F_{n-1}+F_{n-2}$），恒等式$F_{2n}=F_{n}^{2}+F_{n-1}{2}$其实并不成立（比如$n=2$时，$F_{4}=3$，而$F_{2}^{2}+F_{1}{2}=1+1=2≠3$）。正确的对应恒等式应该是**$F_{2n-1}=F_{n}^{2}+F_{n-1}{2}$**，比如：

• $n=2$时，$F_{3}=2=F_{2}^{2}+F_{1}{2}=1+1=2$，成立；
• $n=3$时，$F_{5}=5=F_{3}^{2}+F_{2}{2}=4+1=5$，成立；
• $n=4$时，$F_{7}=13=F_{4}^{2}+F_{3}{2}=9+4=13$，成立。

我猜你可能是下标笔误，下面我们用楼梯拆分的思路来证明这个正确的恒等式，思路完全适用于这类组合证明。

步骤1：建立斐波那契数和楼梯走法的对应关系 #

我们把你的$F_{k}$对应成爬$k-1$阶楼梯的总走法数（每次可以走1步或2步）：

• $F_{1}=1$ → 爬0阶楼梯（原地不动），只有1种方法；
• $F_{2}=1$ → 爬1阶楼梯，只能走1步，1种方法；
• $F_{3}=2$ → 爬2阶楼梯，两种走法（1+1、直接走2步）；
• $F_{k}=F_{k-1}+F_{k-2}$ → 爬$k-1$阶楼梯的走法数 = 爬$k-2$阶的走法数（最后一步走1步） + 爬$k-3$阶的走法数（最后一步走2步），完美匹配递推公式。

这样，正确的恒等式$F_{2n-1}=F_{n}^{2}+F_{n-1}{2}$就翻译为：爬$2n-2$阶楼梯的总走法数 = (爬$n-1$阶楼梯的总走法数)² + (爬$n-2$阶楼梯的总走法数)²。

步骤2：用楼梯拆分分类讨论 #

我们把爬$2n-2$阶楼梯的所有走法分成两类互斥且穷尽的情况：

第一类：走法中恰好在第$n-1$阶有停留 #

也就是说，我们先完整爬完前$n-1$阶，再爬后$n-1$阶（因为$2n-2=(n-1)+(n-1)$）。

• 爬前$n-1$阶的总走法数是你的$F_{n}$；
• 爬后$n-1$阶的总走法数也是你的$F_{n}$；
  所以这类走法的总数是$F_{n} \times F_{n} = F_{n}^{2}$。

第二类：走法中从未在第$n-1$阶停留过 #

这意味着，我们必然有一步是直接从第$n-2$阶走到第$n$阶（跳过了第$n-1$阶），这一步是长度为2的跨步。这一步把楼梯分成了两个独立的部分：

• 左边部分：第1阶到第$n-2$阶，共$n-2$阶，总走法数是你的$F_{n-1}$；
• 右边部分：第$n$阶到第$2n-2$阶，共$n-2$阶，总走法数也是你的$F_{n-1}$；
  所以这类走法的总数是$F_{n-1} \times F_{n-1} = F_{n-1}^{2}$。

步骤3：合并两类情况 #

爬$2n-2$阶楼梯的总走法数就是这两类的和，即：
$$F_{2n-1}=F_{n}^{2}+F_{n-1}{2}$$

这就完成了证明！核心思路是通过中间位置的停留与否，把所有走法拆分成两个互斥的集合，分别计算它们的数量，正好对应斐波那契数的平方和。

内容的提问来源于stack exchange，提问作者Student