Notons $S(n)$ le nombre de façons de descendre un escalier à $n$ marches. On a $S(1)=1$, $S(2)=2$ (ou bien on descend deux fois une marche, ou bien on descend deux marches d'un coup), et $S(3)=4$ : ou bien notre premier pas descend de trois marches, et on a fini, ou bien il descend de deux marches, et il reste un escalier à une marche à descendre, ou bien il descend d'une seule marche, et il reste encore un escalier de deux marches à descendre. Autrement dit, $S(3)=1+1+S(2)=4$.
Cherchons maintenant une formule de récurrence pour $S(n)$ lorsque $n$ est supérieur ou égal à $4$. On raisonne en fonction du premier pas :
- ou bien on descend une seule marche : dans ce cas, il reste un escalier à $n-1$ marches à descendre, et donc $S(n-1)$ possibilités;
- ou bien on descend deux marches : dans ce cas, il reste un escalier à $n-2$ marches à descendre, et donc $S(n-2)$ possibilités;
- ou bien on descend trois marches : dans ce cas, il reste un escalier à $n-3$ marches à descendre, et donc $S(n-3)$ possibilités.
On a donc la formule de récurrence
$$S(n)=S(n-1)+S(n-2)+S(n-3).$$
Il nous faut calculer $S(17)$. Plusieurs méthodes sont possibles. On peut par exemple utiliser un algorithme sous Python :
def S(n):
if n<1:
return 0
elif n==1:
return 1
elif n==2:
return 2
elif n==3:
return 4
else:
return S(n-1)+S(n-2)+S(n-3)
On trouve $S(17)=19513$. On pouvait aussi utiliser un tableur en rentrant 1 dans la cellule A1, 2 dans la cellule A2, 4 dans la cellule A3, =A1+A2+A3 dans la cellule A4, et en étirant cette cellule vers le bas.
