Récurrence forte

[invite1d87dad9]

Bonjour, je dois résoudre cette exercice :

Montrer que tout naturel supérieur ou égal à 8 peut s'écrire sous la forme 3a + 5b avec a et b naturels.

Voici mon raisonnement :

Par récurrence forte sur n > 7 :

Init : 8 = 3*1 + 5*1, 9 = 3*3 + 5*0 et 10 = 3*0 + 5*2.

Hérédité : Soit n un naturel supérieur ou égal à 10. Supposons que pour tout k naturel compris entre 8 et n, la propriété soit vérifiée.

n + 1 = (n - 2) + 3, or n - 2 est compris entre 8 et n donc il existe un couple de naturels (a, b) tels que n - 2 = 3a + 5b.

Ainsi, n + 1 = 3a + 5b + 3 = 3 (a + 1) + 5b où a + 1 est naturel.

Récurrence établie.

Qu'en pensez-vous?
-----

[invitedfbee294]

3a + 5b = 3a + 3b + 2b = 3(a+b) + 2(b) voilà... tu peux écrire tous les multiples de 3, et ajouter 2 une fois ou deux pour avoir les autres.

[invite1d87dad9]

J'avais déjà pensé à ça mais l'exercice demande d'utiliser une récurrence... Du coup je me demande si ma récurrence convient.

[invite1d87dad9]

Personne pour répondre?

[A voir en vidéo sur Futura]

[Anonyme007]

Bonjour,
Moi, je n'ai qu'à te dire très bien.
J'admire ton raisonnement. C'est bien.

[invite1d87dad9]

Admirer, c'est pas un peu exagéré?

[invitedfbee294]

tu veux des suites, tu vas en avoir :

n = 3a + 5b
n+1 = 3c + 5d

on suppose cela vrai pour n :

n+1 - n = 3(c-a) + 5(d-b) = 1

3 et 5 sont premiers entre eux donc d'après bézout il existe des entiers Naturels x et y tel que :

c - a = x
d - b = y

on remplace :

n+1 = 3(a+x) + 5(b+y)
n+1 = 3a+5b + 3x+5y
n+1 = 3a+5b + 1
n+1 = n + 1


j'ai du mal à comprendre ton raisonnement, tu dis que c'est vrai pour n-2 et le montre pour n+1, mais entre les deux ?

[Anonyme007]

Bonjour @Poire Mathert ( et les autres aussi ) :

Non, je n'exagère pas, simplement parce que ton idée d'utiliser une récurrence pour établir cet exercice m'inspire beaucoup de choses.
Utiliser une récurrence à cet exercice me fait penser à l'existence d'une possibilité de prolonger cette meme idée que tu as appliqué, pour établir l'un des problèmes ouverts, difficile d'accès qui harasse tous les mathématiciens à l'heure actuelle. Il s'agit du célèbre problème suivant qui figure ici : https://fr.wikipedia.org/wiki/Conjecture_de_Goldbach et qui n'est pas encore résolu depuis qu'il a été formulé par quelques savants arabes d'Andalousie, ou du grand Maghreb, au temps médiéval. J'ai perdu les sources dont j'ai pu tiré ça. Mais peu importe.

Cordialement.

[albanxiii]

Anonyme007, merci de stopper là le hors sujet.

[invite51d17075]

tu veux des suites, tu vas en avoir :
…….

Le but était d'en proposer une.
et celle proposée est simple et efficace.
dans un exercice, sachant qu'un élève ou étudiant en a de nombreux à résoudre, le mieux est parfois l'ennemi du bien.
d'autant que je doute que Bézout soit à son programme !

[mh34]

Anonyme007 vous n'êtes plus autorisé à poster sur ce fil.

[invite9dc7b526]

Quand tu fais une démonstration par récurrence tu as le choix de l'entier sur lequel porte la récurrence. Ici il faut montrer qu'une certaine propriété est vraie pour tout entier n supérieur à 8 mais ta récurrence n'a pas de raison de porter sur n. Il est plus simple de raisonner sur le groupe d'entiers {3m,3m+1,3m+2} et de faire une récurrence sur m. Le cas 8 est à traiter à part et premier cas est m=1 i.e. {9,10,11} dont on voit immédiatement qu'il peuvent être représentés sous la forme voulue, et si la propriété est vraie pour un m>=1 alors elle est trivialement vraie pour m+1.

dans cet exercice on ne gagne pas grand-chose mais dans d'autres situations ça peut être utile de choisir la bonne variable.

[invite1d87dad9]

Je suis assez surpris par les propos de Anonyme007 mais soit.

"c'est vrai pour n-2 et le montre pour n+1, mais entre les deux ?"

Je ne vois pas trop en fait...

J'ai supposé dans mon hypothèse de récurrence que la propriété est vérifiée pour tout entier compris entre 8 et n pour n supérieur ou égal à 10. Donc n-2 est supérieur ou égal à 8 et est donc compris dans l'intervalle [|8,n|] ce qui me permet d'écrire n - 2 = 3a + 5b pour certains a et b naturels.

Comme je le vois, on sait qu'à l'initialisation, la propriété est vérifiée pour n = 8, n = 9 et n = 10. Donc c'est aussi vrai pour n = 11. Or comme c'est vrai pour n = 8, n = 9, n = 10 et n = 11, ça l'est aussi pour n = 12 etc...

Aussi je ne comprends pas la logique de ta preuve (je connais Bézout, ça n'est pas le problème ici).

[invite51d17075]

Je ne vois pas trop en fait...

moi non plus !
comme ta récurrence porte sur une formulation de n+2 et qu'on te demande de le prouver à partir de n=10,
il est logique que l'initialisation soit sur les trois premiers termes 8,9 et 10.
et le reste de ta démo est très propre pour moi.
cordialement.

[azizovsky]

en suivant ta récurrence , soit la proposition est vraie pour n càd n=3p+5q ,

pour n+1 = 3p+5q+1 = 3p+3+5q-2=3p'+5q+3-5

n+1= 3a+5b

[Médiat]

azizovsky, cette démonstration est incomplète (telle quelle, elle ne marche pas)

[azizovsky]

azizovsky, cette démonstration est incomplète (telle quelle, elle ne marche pas)

ok,le reste stp avant

[Médiat]

ok,le reste stp avant

 Cliquez pour afficher

Si q=0, b n'est pas naturel, d'ailleurs comme la propriété est vrai pour 0, cela démontrerait que c'est vrai pour tout n, alors que c'est faux pour n=1 par exemple

[azizovsky]

 Cliquez pour afficher

Si q=0, b n'est pas naturel, d'ailleurs comme la propriété est vrai pour 0, cela démontrerait que c'est vrai pour tout n, alors que c'est faux pour n=1 par exemple

Merci bcp chef .(tu m'a épargné une nuit blanche)

[invite1d87dad9]

Merci pour vos réponses.