Perso je l'aurais fait empiriquement :

1 marche --> 1 façon (1)
2 marches --> 2 façons (11 ou 2)
3 marches --> 3 façons (111 21 12)
4 marches --> 5 façons (1111 112 121 211 22)
5 marches --> 8 façons (11111 1112 1121 1211 2111 212 221 122)
6 marches --> 13 façons (111111 11112 11121 11211 12111 21111 2112 2121 2211 1212 1221 1122 222)
...

C'est marrant on retrouve la suite de fibonacci : n+1=n+n-1

Pour le prouver, je sais pas trop, essaye de le faire par récurrence mais j'avoue que les maths ça remonte à un petit moment maintenant :)

C'est bon j'ai trouve !
C'est la suite de fibonacci donc on trouve :
1 -> 1
2 -> 2
3 -> 3
4 -> 5
5 -> 8
6 -> 13
7 -> 21
8 -> 34
9 -> 55
10 -> 89
11 -> 144
...

PS : Je n'ai pas trouver seul, mon prof de math ma du montrer comment faire ^^ .

J'ai vu la reponse APRES avoir trouver la reponse =) .