跳 1 或 2 英寸走完 100 英寸：路径数

How many different paths can the flea travel by?

专题: Brainteaser / 脑筋急转弯
难度: L4
来源: QuantQuestion

题目详情

一只跳蚤要从两点之间前进，总距离 100 英寸。它每次只能朝同一方向跳 1 英寸或 2 英寸。

问：它一共有多少种不同的跳法（路径）能恰好走完 100 英寸？

A flea is going between two points which are 100 inches apart by jumping (always in the same direction) either one inch or two inches at a time. How many different paths can the flea travel by?

解析

设 $a_n$ 为走完 $n$ 英寸的跳法数。

最后一步若跳 1 英寸，则前面是走完 $n-1$ 的任意跳法；若跳 2 英寸，则前面是走完 $n-2$ 的任意跳法，因此

a_n=a_{n-1}+a_{n-2},\quad a_0=1,\ a_1=1.

所以 $a_n$ 是斐波那契数列，且 $a_n=F_{n+1}$ 。

所求为 $\boxed{a_{100}=F_{101}}$ 。