Récurrence

[tinmar10]

Bonjour tout le monde !

Je cherche de l'aide pour un exercice de maths ...

Voici l'énoncé :

Montrer que les propositions P(n) et Q(n) définies respectivement sur N par : pour tout entier naturel n, P(n) : "2^(3n) - 1 est divisible par 7" et Q(n) : "2^(3n) +1 est divisible par 7" sont héréditaires.
Sont-elles vraies pour tout entier naturel n ?
(Pour Q, on pourra montrer que nonQ(n) est héréditaire).

Alors commençons pour P(n) ...

Suppons que Pn soit vraie pour un certain indice n, on a 2^(3n) - 1 congru à 0 modulo 7
Or 2^(3(n+1)) - 1 = 2^(3n+3) -1
= 2^(3n) * 2^3 -1
= 2^(3n) *8 -1

Et là je suis bloqué pour montrer que 2^(3n) *8 -1 est congru à 0 modulo 7 ... Si quelqu'un pouvait me mettre sur la voie
-----

[bongo1981]

Tu peux peut-être l'écrire d'une autre façon ?


Et là ça ne doit pas être trop dur de conclure

[invitee6ea268a]

Bonjour,
Tu peux aussi dire que 2^(3n) = (2^3)^n = 8^n

On ecrit alors 8^n - 1^n doit etre multiple de 7.
1) tu demontres que c'est vrai au premier rang
2) tu sippose que c'est vrai au rang n. Puis tu demontres que c'est vrai auy rang (n+1)

Donc allons-y. Pour cela tu utilise l'egalite remarquable qui dit que :
a^n-b^n = (a-b).SOMME (i=0 à n-1) (a^i.b^(n-i)).

au rang n+1, on a a^(n+1)-b^(n+1) = (a-b).SOMME (i=0 à n) (a^i.b^(n-i)).
On sort le terme de rang n de la somme.
On a alors a^(n+1)-b^(n+1) = a^n.(a-b).SOMME (i=0 à n-1) (a^i.b^(n-i)).
et donc a^(n+1)-b^(n+1) = a^n(a^n-b^n).

Or, a^n est entier donc si a^n-b^n est multiple de 7, a^(n+1)-b^(n+1) aussi.

PS: tu pouvais faire la demo directement on remarquant que (a-b)=8-1=7...
On a donc un 7 en facteur dans le terme a^n-b^n ce qui montre bien que c'est un multiple de 7 (car la somme donne un entier).

As tu compris ou j'explique plus clairement?

[tinmar10]

Oui j'ai bien compris, merci beaucoup ...

Après on me demande de dire si ces 2 propositions sont vraies pour tout entier n , on vient de montrer l'hérédité des 2 propositions, il suffit de regarder si P0 et Q0 sont bons non ?

Ainsi ça donnerait pour Pn :

2^(3*0) - 1 = 0, qui est bien divisible par 7

Et pour Qn ça donnerait :

2^(3*0) + 1 = 2, qui n'est pas divisible par 7

Alors Pn est vraie pour tout entier naturel n mais Qn ne l'est pas ?

[A voir en vidéo sur Futura]