階段の上がり方の漸化式による計数

1歩につき1段又は2段上がるとき、n段の階段の上がり方の数x_nは、最後の1歩が1段か2段かで分けて x_n＝x_(n−1)＋x_(n−2)（x_1＝1、x_2＝2）を満たし、x_10＝89である。

順に x_3＝3、x_4＝5、x_5＝8、x_6＝13、x_7＝21、x_8＝34、x_9＝55 となる。