1、背景

最近在看《剑指offer(第二版)》时，Fibonacci数列一节中提到了青蛙跳台阶的进阶版，问题描述为：一只青蛙一次可以跳上1级台阶，2级台阶…，也可以跳上n级台阶，问青蛙跳上n级台阶共有多少中跳法？书中提到了用数学归纳法可以证明跳的方法有 f(n)=2n−1种，本人杠精非要运用高中知识给其证明一下子，然后再给出求解代码。

2、简单的数学归纳法证明

其实这东西证明很简单，只是大家可能忘记高中的知识了，下面给出数学归纳法证明。首先分析一下跳上n级台阶的方法数 f ( n ) f(n) f(n)的表达式应该为：

简要分析一下上式：因为青蛙如果先跳1级台阶，则剩余跳法为 f(n−1)；若先跳2级台阶，则剩余跳法为f(n−2)；以此类推，到先跳n级台阶，则剩余跳法为 f(0)，注意一下此处 f(0)==f(1)==1。

获得上式之后就可以开始推导了，首先进行移项处理：

f(n)−f(n−1)=f(n−2)+...+f(1)+f(0)

然后我们可以惊奇的发现等号右端项就是 f(n−1)，因此我们可以得到下式：

f(n)−f(n−1)=f(n−1)→f(n)=2∗f(n−1)

，然后下面就可以开始高中数学题了，嘿嘿嘿。

f(n)=2∗f(n−1)f(n−1)=2∗f(n−2)f(n−2)=2∗f(n−3)......f(2)=2∗f(1)f(1)=1∗f(0)

到这里可能大家就明白了，把所有的等式进行累乘，之后因为  f(0)==f(1)==1，所以只有n−1个2相乘，最终得到： f ( n ) = 2 n − 1

3、求解代码

就是把上述表达式进行代码化就行咯，有点侮辱智商的意思。

long long FrogJump(int n)
{
  return (long long)pow(2, n-1);
}