Recurrence

[phileas92]

Bonjour, je suis bloqué sur un exercice et n'est aucune idée pour le résoudre.
Je suis en Prepa PCSI 1 er année


exercice :

Montrer à l'aide d'un raisonnement par récurrence que, pour tout n ∈ ℕ tel que n ≥ 8, il existe (a,b) ∈ ℕ^2 tel que : n = 3a + 5b

Merci de vos réponses.

[zygomatique]

salut

deux exemples ::

http://www.ilemaths.net/sujet-arithmeti ... 97338.html
lycee/arithmetique-t159718.html

[phileas92]

Merci beaucoup, je vais tout se suite regarder !

[phileas92]

Apres avoir regarder je n'ai pas dutout compris comment faire..

[zygomatique]

n = 3a + 5b

3(a + 2) + 5(b - 1) = ... ?

[phileas92]

= 3a + 6 + 5b -5
=3a + 5b +1
= n + 1

j'ai compris merci beaucoup

[Ben314]

Salut,
Comme on t'impose de procéder par récurrence (ce qui n'est pas forcément le plus subtil, mais bon...) ça signifie que, partant du fait supposé vrai qu'un certain entier n>=8 peut s'écrire sous la forme n=3a+5b avec a,b dans N il faut que tu en déduise que n+1 s'écrit lui aussi sous la forme n+1=3a'+5b' avec a',b' dans N (évidement, ça ne risque pas d'être les même a et b que pour n !!!).
Donc le but, c'est de trouver a' et b' de façon à ce que ça marche en utilisant évidement l'hypothèse n=3a+5b (c'est le principe même d'une récurrence). Ici, il n'y a pas 36 façon d'utiliser l'hypothèse en question : le seul truc qu'on peut écrire c'est que cette hypothèse signifie que n+1=3a'+5b' équivaut à 3a+5b+1=3a'+5b', c'est à dire 1=3(a'-a)+5(b'-b).
Et là, si on a pas fait d'arithmétique, ben on y va en tâtonnant : les multiples de 3, c'est ...,-9,-6,-3,0,3,6,9,... ceux de 5 c'est ...-10,-5,0,5,10,... (a'-a et b'-b sont entiers mais peuvent être négatifs) et on voit qu'il y a par exemple comme solution 6-5=1 c'est à dire a'-a=2 et b'-b=-1 soit encore a'=a+2 et b'=b-1.
Ça signifie (et c'est ce que tu as vérifié) que, si n=3a+5b, alors n+1=3(a+2)+5(b-1) ce qui est exactement ce qu'on voulais pour notre récurrence à condition que b>=1 pour que b'=b-1 soit positif.

Comment faire lorsque b=0 ? (la réponse peut se trouver dans le laïus çi dessus si on le lit correctement...)

[phileas92]

Merci beaucoup, j'ai bien mieux compris maintenant !

Merci encore et bonne soirée !

[Leptospire]

Bonsoir, je relance ce fil après 5 ans d'inactivité
Je réagis à la dernière phrase de Ben314, le cas b=0.
J'ai procédé de la même manière pour la partie précédente mais je me trouve à ce cas précis.
Quand b=0, on a donc n=3a <=> n+1 = 3a + 1 <=> n+1 = 3a + (3x2 - 5x1) <=> n+1 = 3(a+2) - 5x1 ce qui ne marche pas puisque, il est nécessaire de le rappeler, (a;b) appartient à N².
Qu'ai-je donc mal compris ?

[Vassillia]

Bonjour, comme te l'a indiqué Ben314 on veut 1=3(a'-a)+5(b'-b)
or pour 3(a'-a) on peut choisir ...,-9,-6,-3,0,3,6,9,...
et pour 5(b'-b) on peut choisir ...,-10,-5,0,5,10,...

Dans un premier temps, on a prit b'-b < 0 en choisissant les nombres en rouge donc c'est embetant si b=0
Du coup, pour se rattraper, on peut essayer a'-a < 0 en choisissant quels nombres ?
Certes, ça va être embetant si a<3 mais tu devrai pouvoir en déduire ce que tu cherches quand même car on n'aura jamais à la fois b=0 et a<3.

[Leptospire]

Bonjour Vassilia,

Tout d'abord, merci beaucoup pour votre réponse rapide et précise.
Je me suis rendu compte de différentes erreurs que j'avais commis dans mon raisonnement comme par exemple mon idée qu'un nombre dans N ne peut pas être négatif...
Votre dernière phrase est géniale, je n'y avais pas pensé alors que c'était en face de moi.
Le but est donc de montrer que dans les deux cas, b=0 et a<3, Pn+1 est vraie. Mais comment y arriver ? Parce que, si j'ai réussi à prouver Pn+1 pour b>=1 et pour a'-a<0 (j'en profite pour répondre à votre question, l'arrangement 3 x -3 + 5 x 2 marche dans ce cas), la cas b=0 me pose toujours problème et pour a'-a<0, l'ayant prouvé, puis-je dire que c'est équivalent au cas a'<a donc au cas a'<3 pour n+1 ?

Pardonnez moi pour toutes ces interrogations mais je me sens tellement proche de la réponse que mon esprit est rentré en pleine ébullition.

Cordialement,
Leptospire

[Leptospire]

Ou tous simplement : nous voulons montrer que Pn+1 est vraie. Or, on peut écrire 1 sous la forme 3a+5b de deux manières différentes, avec (a'<0 et b'>0) et (a'>0 et b'<0). Si l'on montre que Pn+1 est vraie dans les deux cas, est ce que cela suffit ?

[Vassillia]

Bon tu as trouvé les bons nombres, en fait tu y es presque mais je crois que tu t'embrouilles dans la disjonction des cas, on part de a et b utilisé dans la récurrence pour en déduire a' et b' au rang suivant.

- si et alors tout va bien, on a beaucoup de choix.

- si et , on va prendre 6 et -5 donc et . Tout va bien et

- si et , on va prendre -9 et 10 donc et . Tout va bien et

- sinon et mais c'est pas possible car on aurait et regarde l'énoncé de départ.

[Leptospire]

Bonsoir,
Je viens de remarquer que j'ai, sans le vouloir, intervertit les a'/a et les b'/b. Ainsi, chez moi, les a' et b' sont vos a et b. Cela explique sûrement la confusion.
J'ai remédié à cette petite erreur et je pense avoir compris le raisonnement. Je le détaille tout de même pour en être certain.

Soit (a,b) appartient à N². Par hypothèse de récurrence, on a :
n=3a+5b
Soit (a',b') appartient à N². On a donc :
1 = 3a'+5b'
On distingue 4 cas :

Cas b>=1 et a>=3 :

Alors n+1 = 3a'+5b' + 1
Alors n+1=3a'+5b' + (3a+5b)
Alors n+1 = 3a'+5b' + 3a + 5b
donc n+1 = 3(a'+a) + 5(b'+b)
Or (a'+a,b'+b) appartient à N² donc n+1 = 3k+5k' avec k=a'+a et k'=b'+b
Donc dans ce cas, Pn+1 est vraie.

...

Pour les autres cas je procède de la même manière mais je souhaiterai juste savoir, pourquoi faut-il absolument que a' et b' soient >= ou > à 0 ?

[Vassillia]

Moi, j'avais suivi les notations précédentes à savoir si n=3a+5b alors n+1=3a'+5b' et notre but à nous c'est de trouver a' et b' en fonction de a et b pour prouver cette propriété. C'est bien pour cela que a' et b' doivent être positifs ou nuls.

Tu peux changer les notations, j'ai rien contre mais alors il faut que ce soit cohérent du début à la fin. Ce qui ne va pas dans ta démonstration en l'état c'est que justement je ne sais pas ce que tu appelles a,a',b,b', pas la même chose que moi visiblement donc c'est compliqué à vérifier 

[Leptospire]

Pardonnez-moi, je n'ai pas été assez clair.
J'ai modifié mon message, je pense que c'est plus compréhensible maintenant

[Vassillia]

Soit (a',b') appartient à N². On a donc :
n+1 = 3a'+5b'

Ben non, il faut le prouver justement

Alors n+1 = 3a'+5b' + 1
Alors n+1=3a'+5b' + (3a+5b)

Ben non, puisque 3a+5b=n

Ce que tu dois faire c'est partir de n+1=3a+5b+1 puis remplacer 1 par 6-5 ou -9+10 comme on avait vu ensemble comme ça tu peux factoriser par 3 et 5 et tu vas trouver a' et b'

Ce qu'avait fait Ben314, c'était pour avoir l'idée de par quoi remplacer 1 et justement ça dépend de la valeur de a et b, voir mon message précédent où je distingue les cas.

[Qoosmo]

Pour n=3a+5b HR
n+1=3a+5b+1=3a’+5b’. Donc 3x+5y=1 avec x et y a déterminer et cette dernière équation est résoluble par l’algorithme d’Euclide.

Bien à vous.

Ali

[Leptospire]

Boujour,
Après moult réflexions, j'ai trouvé comment bien rédigé mon exercice.
Merci beaucoup Vassillia pour votre aide et vos petites clarifications. Merci également à Qoosmo, je vais jeter un œil à cette équation.

Cordialement,
Leptospire

[Vassillia]

Tant mieux, ravie d'avoir pu aider, bon courage pour la suite