Recurrence

[Anonyme]

bonjour,
c'est encore moi les gens, la récurrence c'est pas trop mon truc mais j'aime me confronter à des difficultés.
le problème est le suivant :
- soit An le nombre de chaines binaires de longueur n qui contiennent deux << 0 >> consécutifs.
trouver une relation de récurrence pour An?
ça je suis toujours butté sur ce genre de problème.

[Anonyme]

en supposant que An-1 soit le nombre de chaines binaires de longueur (n-1) qui contiennent deux 0 consécutif, on 2 * An-1 chaines de longueur n qui contiennent deux 0 consécutif, puis les chaines de longueur n-1 ne contenant pas deux 0 consécutif mais se terminant pas 0 qui ne sont que (n-2); donc
An = 2* An-1 + (n-2) avec comme condition initiale n> 2, A2 =1 .

j'aimerai avoir d'autres solutions, Merci

[Zavonen]

Désignons par le nombres de sites de longueur n (répondant au critère) et se terminant par 0.
Désignons par le nombres de sites de longueur n (répondant au critère) et se terminant par 0.
Désignons par le nombres de sites de longueur n (répondant au critère) et se terminant par 1.
De sorte que =+
On a les relations de récurrence suivantes:


De sorte que si on considère la suite de Fibonacci classique amorcée avec 0,1
Les sont les termes de cette suite
Les sont les termes de cette suite décalés d'une unité
Les sont les termes de cette suite décalés de 2 unités.