9.1. First-grader Masha, entering the school, each time climbs the school porch stairs, which have 10 steps. Being at the bottom of the stairs or on one of its steps, she can either go up to the next step or jump over one step up (Masha cannot yet jump over two or more steps). What is the minimum number of times Masha needs to enter the school to climb the porch in all possible ways?
Answer: 89. Solution. Note that Masha can climb a porch with one step in one way, and a porch with two steps in two ways: either stepping on each step, or, by stepping over the first step, landing directly on the second.

Let $a_{n}$ be the number of ways Masha can climb a porch with $n$ steps. Since Masha can reach the $n$-th step either from the $(n-1)$-th step or from the $(n-2)$-th step, then $a_{n}=a_{n-2}+a_{n-1}$.

We sequentially calculate: $a_{1}=1, a_{2}=2, a_{3}=1+2=3, a_{4}=2+3=5, a_{5}=3+5=8$, $a_{6}=5+8=13, a_{7}=8+13=21, a_{8}=13+21=34, a_{9}=21+34=55, a_{10}=34+55=89$.

Note that the numbers constructed according to the rule $F_{0}=0, F_{1}=1, F_{n}=F_{n-2}+F_{n-1}(n \geq 2)$ are called Fibonacci numbers. Thus, $a_{n}=F_{n+1}$.