階段の上がり方とフィボナッチ数列

1歩で1段又は2段上がるとき、n段の上がり方の数x_nは、x_n＝x_{n−1}＋x_{n−2}（x_1＝1, x_2＝2）を満たす。

最後の1歩が1段のときx_{n−1}通り、2段のときx_{n−2}通りだから、この漸化式が成り立つ。