Matgs fondamentaux

[youkef-sne]

Bonjour un petit DM que je galere a faire, je vous pose le sujet en esperant avoir de l'aide:

on appel un mot une séquence finie de lettre, par exemple "aabbababbab" est un mot. Étant donné deux mots u et v, on notera uv le mot obtenu en concaténant u avec v.
On étudie la suite de mots (Wi) défini par la récurrence suivante: W(1)=a, W(2)=ab et pour tout i>=3,
W(i)=W(i-1)W(i-2). On a donc:
W(1)=a W(2)=ab W(3)=aba W(4)=abaab.

1) Donner W(5), W(6) et W(7).
2) Monteer que pour tout i>=1, la premiere lettre du mot W(i) est un a.
3) Montrer que pour tout i>=1, le mot W(i) ne contient pas deux b consecutifs.
Piur tout i>=3, on note p(i) le mot obtenu a partir de W(i) en enlevant les deux dernieres lettres. Par exemple,
p(3)=a, p(4)=aba, p(5)=abaaba,..). On cherche maintenant à montrer que pour tout i>=3, le mot p(i) est un palindrome.

4)Montrer que pour tout i>=3, on a la propriété suivante: Si i est pair alors W(i)=p(i)ab, c'est-à-dire que W(i) se termine par ab et si i est impair, alors W(i)=P(i)ba W(i)se termime par ba.
5) en déduire que pour tout i>=6, on a la propriété suivante: Si i est pair alors
p(i)=p(i-2)abp(i-3)bap(i-2) et si i est impair, alors p(i)=p(i-2)bap(i-3)abp(i-2).
cobclure.


voila ce que j'ai faos:
1) W(5)=W(4)W(3)=abaababa
W(6)=W(5)W(4)=abaababaabaab
W(7)=W(6)W(5)=abaababaabaababaababa

2apres j'y arrive pas

[Lostounet]

Hello,
La 2) n'est vraiment pas difficile. C'est quoi la 1ere lettre de chaque W(i) ?
A chaque fois tu ajoutes des termes à droite...
3) Essaye une récurrence forte en utilisant la 2)

[youkef-sne]

Hello,
La 2) n'est vraiment pas difficile. C'est quoi la 1ere lettre de chaque W(i) ?
A chaque fois tu ajoutes des termes à droite...
3) Essaye une récurrence forte en utilisant la 2)

Voila ce que j'ai fais pour la 2:
2) Pa recurrence on a: W(1)=a, W(2)=aba. le mot W(i) et définit par la succession de W(i-1) et W(i-2), et ainsi de suite jusqu'a obtenir W(1) et W(2) qui commebce eux par a donc forcement W(i), commencera toujours par a.

En revanche, on a jamais vu ce que c'etait qu'une recurrznce forte

[Lostounet]

2) Oui par récurrence, Puisque W(1) = a
W(2) = ab

Supposons que pour tout i allant de 1 jusqu'à n, W(i) commence par a
W(n + 1) = W(n).W(n - 1) commence par a

3. Je pense que la récurrence permet aussi de le justifier.

Pour tout i, W(i) se termine soit par a soit par b, or la première lettre du mot suivant est toujours a, donc si W(i) se termine par b, W(i + 1) commencera par a et il n'y aura pas deux b consécutifs lorsque tu concatènes au niveau du raccord.

Qu'as-tu essayé pour la 4?

[youkef-sne]

2) Oui par récurrence, Puisque W(1) = a
W(2) = ab

Supposons que pour tout i allant de 1 jusqu'à n, W(i) commence par a
W(n + 1) = W(n).W(n - 1) commence par a

3. Je pense que la récurrence permet aussi de le justifier.

Pour tout i, W(i) se termine soit par a soit par b, or la première lettre du mot suivant est toujours a, donc si W(i) se termine par b, W(i + 1) commencera par a et il n'y aura pas deux b consécutifs lorsque tu concatènes au niveau du raccord.

Qu'as-tu essayé pour la 4?

4) On a: W(1)=a et W(2)=ab.
2 est pair et dpnc termine par ab. Donc tous les mots au rang 2n termineront par ab.
1 est impair et W(1)=a. donc le mot terminera par a, domc par ba.

[N.L]

Pour la 4 , cela doit encore être une récurrence , non ? Mais je vois pas comment la faire par contre ?

[youkef-sne]

Pour la 4 , cela doit encore être une récurrence , non ? Mais je vois pas comment la faire par contre ?

Ma reponse me semble juste pour la question 4 et pourtant je n'ai pas fais de recurrence

[N.L]

oh pardon je n'avais pas vu ta réponse , ta réponse parait juste mais est ce que c'est suffisant pour le prouver au rang i , je ne sais pas ...

[youkef-sne]

oh pardon je n'avais pas vu ta réponse , ta réponse parait juste mais est ce que c'est suffisant pour le prouver au rang i , je ne sais pas ...

C'est exactement sa le probleme, parce que en admettant que si i est impair et que la derniereettre est un a, je ne sais pas comment prouver dans ce cas la que l'avant derniereettre est un b de favon a ce que le.mot pi se termine par ba.

[N.L]

quelqu’un à t'il une idée ?

[youkef-sne]

Je bloque a la question 5 quelqu'un pourrait m'aider

[Suisse_hide]

oh pardon je n'avais pas vu ta réponse , ta réponse parait juste mais est ce que c'est suffisant pour le prouver au rang i , je ne sais pas ...

Il est évident qu'il faut montrer la propriété de la question 4 à l'aide d'une récurrence. Il suffit pas de montrer que ça marche pour i pour prouver à i+1.
Comme i >= 3 , alors il faut réaliser l'initialisation à W(3) pour les impairs et à W(4) pour les pairs.
Ensuite on pose W{2i+1} = P{2i+1} ba -impair et W{2i+2} = P{2i+2} ab -pair
et on résoud à i+1

Bonne continuation du DM de FMI