[ $[\quad$ Rule of product $\quad]$

a) Leshа climbs a ladder with 10 steps. In one jump, he can either go up one step or two steps. In how many ways can Leshа climb the ladder?

b) When descending the same ladder, Leshа skips some steps (he can even skip all 10). In how many ways can he descend the ladder?

#
a) Let $a_{n}$ denote the number of ways to climb a staircase of $n$ steps, adhering to the conditions of the problem.

Obviously, $a_{1}=1, a_{2}=2$.

Suppose Petya jumps onto a staircase of $n>2$ steps. If the first jump is to two steps, then he has $n-2$ steps left to jump, and the number of ways to complete the ascent is $a_{n-2}$. If the first jump is to one step, then the number of ways to complete the ascent is $a_{n-1}$. Therefore,

$a_{n}=a_{n-1}+a_{n-2}$

This equality allows, knowing $a_{1}$ and $a_{2}$, to sequentially compute all $a_{\mathrm{n}}$ (in this case, the well-known Fibonacci numbers will be obtained):

$a_{3}=3, a_{4}=5, a_{5}=8, a_{6}=13, a_{7}=21, a_{8}=34, a_{9}=55, a_{10}=89$.

b) Each of the 9 steps (except the last one) Petya can either skip or not skip independently of which of the upper steps he has stopped on. Therefore, the number of ways to descend the staircase is $2^{9}$.

## Answer

a) 89 ways; b) 512 ways.