Cliquez pour afficher

Je donne juste une idée, je ferai les calculs plus tard :

Pour un escalier à 2k marches :

- si une suite de marches se termine par 2 alors elle donne naissance à une nouvelle façon de monter l'escalier à 2k+2 marche.

- si une suite de marches se termine par 4 alors elle ne donne naissance à aucune nouvelle façon de monter l'escalier à 2k+2 marche.

On passe donc de à en ajoutant le nombre de suite de marches qui se terminent par 2.

Exemple pour un escalier à 6 marches pour passer à 8 marches :

2-2-2 donne naissance à 2-2-2-2 ou 2-2-4 donc +1

2-4 donne naissance à 2-4-2 donc +0

4-2 donne naissance à 4-2-2 ou 4-4 donc +1

Il y a 3 façon de monter un escalier à 6 marches, et il y aura donc 5 façons de monter un escalier à 8 marches et 8 de monter 10 marches.

 Cliquez pour afficher

C'est un problème classique.
Pour monter n marches le dernier pas a monté 2 ou 4 marches et donc le nombre façons de monter un escalier de n marches est la somme de celles pour un escalier de n-2 marches et celles pour un escalier de n-4 marches.
Il y a une façon de monter un escalier de 0 marches et une seule de monter un escalier de 2 marches. On peut déduire les autres à partir de ces deux dernières.

Ce qui donne :



On peut vérifier U = {1,0,1,0,2,0,3,0,5,0,8,0,13,...}

On remarque que c'est la suite de Fibonacci intercalée avec des 0 pour les nombres de marches impaires.