Dm

[invite0937202d]

Bonjour,

J'ai un Dm a faire, mais je n'arrive pas une question de celui-ci. Voici le sujet:
Camille est de plus en plus stressée au fur et à mesure que le bac de français approche. Il faut que ca marche! La prenant mot pour mot, ses copines l'emmène dans les ruelles, pù les escaliers ne manquent pas.

Le premier escalier compte trois marches et Camille, qui adore monter les marches une à la fois ou deux à la fois, a constaté qu'elle pouvait monter les escalier de trois manières différentes (voir dessin).

2) Désignons par u(n) avec n un indice, le nombre de maières pour Camille de monter l'escalier à n marches
Justifier que u(n+2)=u(n+1)+u(n) avec (n+2), (n+1) et n des indices.

Je n'arrive pas cette question, pouvez-vous m'aider?
-----

[danyvio]

Soit un escalier de n marches, et nécessitant donc U(n) façons de le grimper (peu importe le détail - et surtout ne pas s'en préoccuper ! -)

Ajoutons UNE marche, ce qui donne un nouvel escaliers de n+1 marches.

Pour grimper l'escalier de n+1 marches, il faut ajouter les valeurs suivantes :
U(n) façons de grimper les n premières marches, la dernière marche (celle qu'on a ajoutée) étant gravie seule.
+
U(n-1) = le nombre de façons pour grimper les n-1 premières marches, en terminant en enjambant deux marches (celle qui était la dernière des n et celle qu'on vient d'ajouter).
Donc ... tu vois la règle de récurrence !
Illustration :
(Pour aller plus loin il faut remarquer que pour grimper un escalier de 2 marches, il y a 2 façons : 1,1 ; 2)

On part d'un escalier de 3 marches 3 solutions 1,1,1; 1,2 ; 2,1

A l'escalier de 3 marches on ajoute une marche;
On a alors n(3) façons de grimper en terminant par une marche +
2 facons de grimper en finissant par 2 marches.
Soit dans cet exemple 5 façons de grimper un escalier de 4 marches, ce que tu peux vérifier !