Cours gratuits > Forum > Forum maths || En bas
Problème de récurrence
Message de morpheus21 posté le 25-09-2011 à 12:14:52 (S | E | F)
Bonjour,
Je m'entraîne à la récurrence.
Je fais cet(te) exercice :
Montrer que pour tout enter naturel n (4^n)-1 est un multiple de 3.
J'ai commencé comme ceci :
Initialisation :
pour n = 1, (4^n)-1=3 c'est bien un multiple de 3. La proposition est donc vraie pour n=1.
Hérédité:
On suppose que la proposition est vraie pour n = k avec k un entier supérieur ou égal à 0 soit (4^k)-1 est un multiple de 3 (hypothèse de récurrence).
Montrons alors que pour n = k+1 on obtient aussi un multiple de 3.
c'est à dire montrons que (4^k+1) -1=3a avec a un entier naturel.
C'est là que je bloque.
J'ai brouillonné ça :
(4^k+1) -1 = (4^k)*4-1
Et je cherche un résultat du genre ...=(4^k-1)*?? etc.
Merci de vos futures réponses.
-------------------
Modifié par bridg le 25-09-2011 12:22
Message de morpheus21 posté le 25-09-2011 à 12:14:52 (S | E | F)
Bonjour,
Je m'entraîne à la récurrence.
Je fais cet
Montrer que pour tout enter naturel n (4^n)-1 est un multiple de 3.
J'ai commencé comme ceci :
Initialisation :
pour n = 1, (4^n)-1=3 c'est bien un multiple de 3. La proposition est donc vraie pour n=1.
Hérédité:
On suppose que la proposition est vraie pour n = k avec k un entier supérieur ou égal à 0 soit (4^k)-1 est un multiple de 3 (hypothèse de récurrence).
Montrons alors que pour n = k+1 on obtient aussi un multiple de 3.
c'est à dire montrons que (4^k+1) -1=3a avec a un entier naturel.
C'est là que je bloque.
J'ai brouillonné ça :
(4^k+1) -1 = (4^k)*4-1
Et je cherche un résultat du genre ...=(4^k-1)*?? etc.
Merci de vos futures réponses.
-------------------
Modifié par bridg le 25-09-2011 12:22
Réponse: Problème de récurrence de morpheus21, postée le 25-09-2011 à 12:34:47 (S | E)
Re,(désolé pour le double-post)
J'ai trouvé un exercice du même type ils l'ont résolu comme ceci :
On a donc (4^k)-1=3a -> (4^k)=3a+1 (hypothèse de récurrence)
alors (4^k+1)-1=4*(4^k)-1
=4*(3a+1)-1
=12a+4-1
=12a+3
=3*4*a+3
=3(4a+1) avec a un entier naturel.
On en déduit que (4^k+1)-1 est bien un multiple de 3.
Conclusion
La proposition est vraie donc pour tout n appartenant a grand N 4^n-1 est un multiple de 3.
Cours gratuits > Forum > Forum maths
