#### 原题目
假设现在有 N 级台阶，每次可以走 1 步或者 2 步，求解一共有多少种走法。
#### 涉及领域
* [斐波那契数列](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97)
* 初等代数（延伸）
#### 递归思路
首先考虑最简单的情况。
* 如果只有 1 级台阶，那显然只有一种跳法。
* 如果有 2 级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳 1 级；另外一种就是一次跳 2 级。
然后讨论一般情况：
* 把$n$级台阶时的跳法个数看成是$n$的函数，记为$f(n)$。
* 当$n=1$时，$f(1)=1$，当$n=2$时，$f(2)=2$
* 当$n>2$时，
第一次跳的时候就有两种不同的选择：
一是第一次只跳 1 级，此时跳法数目等于后面剩下的$n-1$级台阶的跳法个数，即为$f(n-1)$；
二是第一次跳 2 级，此时跳法数目等于后面剩下的$n-2$级台阶的跳法个数，即为$f(n-2)$。
因此有：$n$级台阶时的不同跳法个数为$f(n)=f(n-1)+(f-2)$。
因此就有以下借助编程解决的思路
```c
int compute(int i) {
if (i <= 0) {
return 0;
} elseif (i == 1) {
return 1;
} elseif (i == 2) {
return 2;
} else {
return compute(i - 1) + compute(i - 2);
}
}
```
#### 数学延伸
以上的问题，其实就变成了斐波那契数列推导问题
已知
$$
f(n)=\begin{cases}
1 &n=1 \\\\
2 &n=2 \\\\
f(n-1)+f(n-2) &n>2,{n}\in{N^+}
\end{cases}
$$
求 $f(n)$ 的表达式
维基百科提供的初等代数解法是 **构建等比数列**。
为何要尝试用数列的方向解决呢？
原因是 $f(n)=f(n-1)+f(n-2)$ 确实和数列中 **描述当前项，前一项和前两项的关系** 的关系式类似。
那么求 $f(n)$ 就可以转化为以下命题：
求符合如下关系的数列 $\\{a_n\\}$ 的通项公式。
$$
a_n=a_{n-1}+a_{n-2} (n>2, n\in{N^+})
$$
那么，如下构建等比数列
$$
f(n)+af(n-1)=b(f(n-1)+af(n-2))
$$
> 备注：右侧$f(n-2)$的系数$a$可别搞没了，不然就不符合等比数列的定义了
合并同类项，可得：
$$
f(n)=(b-a)f(n-1)+abf(n-2)
$$
从关系式$f(n)=f(n-1)+f(n-2)$可知：
$$
\begin{cases}
b-a =1 \\\\
ab=1
\end{cases}①
$$
换元法，得出一元二次方程：
$$
a^2+a-1=0
$$
* 从这一步开始，$a$是有正负两个解，对应的$b$也会有两个解。
* 因为$a$和$b$只是构建等比数列时临时借用的变量，这里完全可以假定$a>0$，$b>0$。
假定$a>0$，$b>0$，可得：
$$
\begin{cases}
a=\frac{\sqrt{5}-1}{2} \\\\
b=\frac{\sqrt{5}+1}{2}
\end{cases}
$$
至此，把$a$，$b$代入，等比数列构建如下:
$$
\{f(n)+\frac{\sqrt{5}-1}{2}f(n-1)\}: f(n)+\frac{\sqrt{5}-1}{2}f(n-1) = \frac{\sqrt{5}+1}{2}(f(n-1)+\frac{\sqrt{5}-1}{2}f(n-2))
$$
> 但是在之后的说明当中写起来太麻烦了，这里依然还是用$a$和$b$代替，最终目的是**构建**并**确定**等比数列的关系式！
至此，前面所述的等比数列已经确定。条件当中提供了$f(1)$和$f(2)$，那么确定首项就是：$f(2)+af(1)$，根据等比数列的通项式得：
$$
\begin{aligned}
f(n+1)+af(n) &= (f(2)+af(1))b^{n-1}\\\\
&= (2+a)b^{n-1}\\\\
\end{aligned}
$$
* 等比数列通项式: $a_n=a_1q^{n-1}$
* 真正的斐波那契数列，首项应该是从 0 开始，第二项为 1，第三项也为 1，第四项开始才是 2，而这里描述的显然是缺少了前两项的斐波那契数列。
* 这里为了便于计算，带上原数列的第二项，设定等比数列首项为$f(1)+af(0)$，其中$f(0)$由$f(0)=f(2)-f(1)=1$得出
* 因为需要自行构造数列来解答，才 **按规则** 变更首项，但是后一项跟前一项的关系需遵守等比数列规则
所构造的等比数列改变后，变通后的通项式为：
$$
\begin{aligned}
f(n+1)+af(n) &= (f(1)+af(0))b^{n-1}\\\\
&= (1+a)b^{n-1}\\\\
\end{aligned}
$$
由①的第一个式子得$1+a=b$，上式又会变成：
$$
f(n+1)+af(n)=b^n
$$
两边同时除以 $b^{n+1}$，就会得到以下式子：
$$
\frac{f(n+1)}{b^{n+1}}+\frac{af(n)}{b^{n+1}}=\frac{1}{b}
$$
即
$$
\frac{f(n+1)}{b^{n+1}}+\frac{a}{b}\frac{f(n)}{b^n}=\frac{1}{b}
$$
把$\{\frac{f(n)}{b^n}\}$视作另一个数列②，记作$g(n)$，上列式子就会变成：
$g(n+1)+\frac{a}{b}g(n)=\frac{1}{b}$ ③
> 启示：遇到包含$a_{n+1}$和$a_n$的，而且除这两个以外其他都是常量的关系式中，$a_{n+1}$和$a_n$的系数不一样的情况，就应当尝试构造$\\{a_n+x\\}$的等比数列了
再次构造等比数列$\\{g(n)+x\\}$，令其通项式为：
$$g(n+1)+x=-\frac{a}{b}(g(n)+x)$$
变形得
$$g(n+1)+\frac{a}{b}g(n)=-\frac{(a+b)}{b}x$$
由③得：
$$-\frac{(a+b)}{b}x=\frac{1}{b}$$
即$x=-\frac{1}{(a+b)}$
* 这里不需要知道$x$具体是什么值，只要知道它是常量就好。
即所构造得数列$\\{g(n)+x\\}$为等比数列。
那么，回到②的定义可知：
$$g(1)=\frac{f(1)}{b^1}=\frac{1}{b}$$
那么数列$g(n)$就可以表示为
$$g(n)+x=(-\frac{a}{b})^{n-1}(g(1)+x)=(-\frac{a}{b})^{n-1}(\frac{1}{b}+x)$$
到了这里，基本上可以开始整理一下我们得到的玩意儿：
$$
\begin{cases}
x=-\frac{1}{(a+b)} \\\\
g(n)+x=(-\frac{a}{b})^{n-1}(\frac{1}{b}+x) \\\\
g(n)=\frac{f(n)}{b^n} \\\\
a=\frac{\sqrt{5}-1}{2} \\\\
b=\frac{\sqrt{5}+1}{2}
\end{cases}
$$
由上面的式子经过不断的代入换元，最终是可以得出：
$$f(n)=\frac{\sqrt{5}}{5}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n]$$
那么，由于我们推导公式的时候，把首项往前推了一项。因此对应到这道题，要把首项往后推，即令$F(n)=f(n+1)$，也就是：
$$
F(n)=\frac{\sqrt{5}}{5}[(\frac{1+\sqrt{5}}{2})^{n+1}-(\frac{1-\sqrt{5}}{2})^{n+1}]
$$
这才是题目所求的 $f(n)$
由此，斐波那契数列公式推导完成！在实际编程当中，若能直接使用此公式解决，性能可能会是递归的几倍之多。
> 但是往往实际业务会比这个复杂得多，因此图个乐呵即可。递归才是相对通用的解决方案。
台阶走法问题：递归编程与斐波那契数列推导过程初探