Inscription / Connexion Nouveau Sujet
Recurrence
Bonjour, j'ai besoin d'aide svp.
Prouvez que pour tout entier naturel n, 2^(3n) - 1 est un multiple de 7.
Ca revient donc à prouver que 2^(3n) - 1 = 7q.
J'ai prouvé que P0 est vraie, mais je bloque pr la suite.
édit Océane : niveau modifié, merci d'en faire autant dans ton profil
salut
Donc tu as prouvé que P(0) est vraie.
donc supposons que pour un entier n supérieur à 0, p(n) est vraie.
Démontrons que p(n+1) est vraie.
23n-1=7q
23n=(23)n=8n.
Astuce: pense à multiplier par 8.
Bonjour,
par récurrence, pour prouver l'hypothèse d'hérédité il faut supposer P(n) et en déduire P(n+1).
Autrement dit, tu sais que 23n - 1 = 7q et tu cherches à prouver qu'il existe q' tel que 23(n+1) - 1 = 7q'.
Comment procède-t-on? Et bien tu pars de 23(n+1) - 1 et tu essaye de faire apparaitre 23n - 1 ou 23n.
Ainsi tu sais que
23(n+1) - 1 = 2^3 23n - 1 = 8.23n - 1.
Ainsi tu utilises ton hypothèse de récurrence 23n - 1 = 7q.
soit 23(n+1) - 1 = 8.(7q + 1) - 1 = 7(8q + 1)
Ainsi, tu as prouvé l'hypothèse d'héridité...
Dans une récurrence, l'idée c'est de faire apparaitre à partir du cas (n+1) un peu du cas (n) pour pouvoir utiliser l'hypothèse de récurrence...
J'espère avoir été clair. 
On pouvait aussi astucieusement remarquer que
32n - 1 = 8n-1 = (8 - 1) (8n-1 + 8n-2 + ... + 8 + 1) = 7(8n-1 + 8n-2 + ... + 8 + 1)
Annuler
connectez vous