Raisonnement par récurrence

[gravitoin]

Bonjour,
Je suis en terminale et ayant fait le raisonnement par récurrence (simple et fort), je me demande s'il ne serait pas possible de supposer une propriété au delà de n+1 (et dans le cas contraire de m'expliquer pourquoi). Par exemple on supposerait une propriété Pn vraie du rang 1 à n (comme dans une récurrence forte) mais aussi de n+2 à 3n (je dis ici 3n mais ca pourrait être 5n+3 ou 8n+4, ce n'est qu'un exemple). Ainsi si l'on démontre que au rang n+1, 3n+1, 3n+2 et 3n+3 notre propriété est vraie alors P(n+1) serait établie. On établirait ainsi que pour tout entier naturel, notre propriété est vraie (en effectuant bien évidemment une initialisation au préalable.)
Pourriez vous m'apporter des éléments de réponses s'il vous plaît.
Je vous remercie d'avance.
-----

[gg0]

Bonjour.

Je ne saisis pas trop ton propos. Soit la véracité de l'hypothèse jusqu'au rang n suffit à démontrer la véracité au rang n+1 (quitte à utiliser dans la démonstration la véracité - à démontrer- pour n+2, n+3, ... 3n), soit tu parles d'autre chose.
Comme c'est très flou, propose un exemple, on comprendra pourquoi tu poses cette question.

Cordialement.

NB : on peut toujours se ramener à la récurrence simple, il suffit de choisir correctement l'hypothèse de récurrence.

[Merlin95]

Ainsi si l'on démontre que au rang n+1, 3n+1, 3n+2 et 3n+3

Ok mais comment tu démontres cela ? Par récurrence ?, non je pense pas sinon ta question n'a aucun sens.

Du coup si ce n'est pas par récurrence, tu as démontré la propriété pour 3n+1, 3n+2 et 3n+3, pour n entier positif ou nul. Donc tu as démontré la propriété pour :
n=0
P(1)
P(2)
P(3)
n=1
P(4)
P(5)
P(6)
...
Donc tu as démontré P(n) pour tout n>0, donc tu n'as plus besoin de récurrence, en principe.

Mais pas sûr d'avoir compris ta question.

[jiherve]

bonsoir
mes math sont loin mais s'il y a récurrence alors la question me surprend et s'il n'y en a pas alors c'est faux ex
|Ln(1/10)| <> 0 est vraie de 1 à 9 de 11 à .. et fausse pour n= 10.
JR

[A voir en vidéo sur Futura]

[gravitoin]

Bonjour,
Je conçois effectivement que mes propos ne soient pas clairs. Je vous dépose donc en pièce jointe une tentative de démonstration qui repose sur ce principe (cette démonstration est probablement voir certainement fausse, mais elle pourra je l'espère vous faire comprendre le principe de ce raisonnement.)
N'hésiter à me dire si il y a des points qui ne sont pas clairs.
Je vous remercie pour vos réponses.

NB : Cette "démonstration" manque de rigueur
NB(2) : J'espère que vous arriverez à lire la pièce jointe.

[jiherve]

Re
il me semble y avoir une coquille

Si n est pair alors 3n+6 et 3n+8 sont pairs, on les divise donc par deux. On obtient
ainsi un entier compris entre (n+2) et (3n+5)

?
JR

[gravitoin]

Bonjour jiherve,

Pouvez vous être plus précis sur la teneur de la coquille ou du moins donner un contre-exemple car je ne vois aucun entier naturel pair, n, tel que (3n+6)/2 ne soit pas compris entre n+2 et 3n+5.

[gg0]

Heu ... ça me semble juste, 3/2*n+3 et 3/2*n+4 sont bien entre n+2 et 3n+5.

Pour une fois, je ne trouve pas de faille dans ce raisonnement, et il y a bien une récurrence simple. C'est écrit simplement et clairement. J'ai repris entièrement le raisonnement, je ne vois pas de faille (il y a des affirmations rapides, mais justes).

[Merlin95]

Par contre pour être complet (j'ai pas regardé les détails mais je fais confiance à priori à gg0, mais je checkerai), il faut l'initialisation « au rang 0 », soit dans ton cas que la proposition est vraie pour ces « k » (k=2, 12, 13, 14, 36, 40, 32), si je ne me trompe pas :
- P(2)
- P(12), P(13), P(14)
- P(36), P(40)
- P(32)

Mais comme il y a un nombre fini de cas à vérifier et que ca serait étonnant que ca soit faux pour ces valeurs de « k » pas très élevés, y'a aucun problème de fond sur cette initialisation.

[gravitoin]

Je vous remercie beaucoup pour vos réponses.
Cependant mon professeur m'avait dit qu'on ne pouvait pas supposer une propriété au-delà du rang n.
Cela ne vous pose-t-il aucun problème que je suppose ma propriété vraie pour des rangs au delà de n?
Merlin95, effectivement j'ai mis un lien vers un site qui montre que cela est vraie pour les petites valeurs de n.

[Merlin95]

Oui c'est un peu exotique je dois y réfléchir.

[gg0]

L'avantage de cette conjecture, c'est qu'elle est déjà fortement initialisée !!

Sinon, je ne cois pas le problème de "au delà de n", on a une propriété P(n) qui est initialisée (largement, mais au moins pour n=1) et il semble bien que pour n>=1, on montre que P(n) ==> P(n+1). La preuve par récurrence ne pose aucune condition sur P.

Je réserve mon avis, mais attendons que d'autres vérifient à leur tour, je peux avoir raté une étape.

Cordialement.

[Nini42]

Désolée d'avance si je me trompe mais dans l'énonciation de (Pn), on nous dit "- pour les entiers (6n+12) et (6n+16) si n est impair" et dans ce qu'il faut montrer pour prouver (Pn+1), on a "; 6n+18 et 6n+22 si n est impair"... ça ne devrait pas être "si n+1 est impair", donc "si n est pair" ?

[jiherve]

re
j'avais raisonné sur la valeur minimale et il n'existe aucun entier pair pour lequel (3n+6)/2 soit égal à n+2 mais peut être me trompe je?
donc n+2 est exclu!
JR

[Merlin95]

Non pas valable, car il faut démontrer aussi les P(f1(j)), P(f2(j)), P(f3(j)), P(f4(j)) pour j=n+1 (si on les a supposé vraie pour n), avec f1|2|3|4(j)=... les fonctions que tu as prises.

[gg0]

Effectivement Nini42, tu as soulevé un lièvre. Je regarde demain.

Cordialement

[Merlin95]

@gravitoin je ne crois pas que ta démonstration par récurrence soit valable (même si dans le détail, il n'y a pas d'erreurs), car les hypothèses (toutes, c'est-à-dire tout ce qui dépend de « n » en gros) doivent aussi être démontrées (par récurrence ou autre) mais je ne crois pas que ce soit le cas, peut-être dans le détail c'est ce que tu as fait (mais je ne pense pas sinon j'imagine que tu ne te poserais pas de question sur "ta récurrence")

Ou il y a une subtilité qui m'échappe ?

[gravitoin]

Merci beaucoup pour vos réponses. Effectivemment Nini42, vous semblez avoir soulevé un problème que je n'avais pas vu jusqu'à présent. Je reviendrai si j'arrive à le corriger (ce dont je doute un peu.) Mais il y a sûrement aussi un problème de fond avec cette méthode comme l'a soulevé Merlin95.

[MissJenny]

Désolée d'avance si je me trompe mais dans l'énonciation de (Pn), on nous dit "- pour les entiers (6n+12) et (6n+16) si n est impair" et dans ce qu'il faut montrer pour prouver (Pn+1), on a "; 6n+18 et 6n+22 si n est impair"... ça ne devrait pas être "si n+1 est impair", donc "si n est pair" ?

c'est là qu'est le problème en effet. On pourrait essayer de s'en tirer en démontrant séparément la conjecture de Syracuse pour les nombres pairs et pour les impairs mais ça ne marche pas non plus.

[gg0]

Après relecture, je confirme le défaut : C'est bien "6n+18 et 6n+22 si n+1 est impair", et la preuve est faite pour n+1 pair.
Et je confirme encore que la méthode est correcte. Il s'agissait bien d'une preuve par récurrence de la propriété P(n) définie par :
"Les nombres entiers de 1 à n>0, de n+2 à 3n+5 compris, et 6n+12 et 6n+16 si n est impair et 6n+14 si n est pair sont tels que la suite de Collatz qui commence par eux finit par passer par 1".
L'initialisation est évidente (pour n=1 ces nombres sont tous connus pour donner des suites de Collatz amenant à 1); reste la démonstration de P(n)==>P(n+1), qui est fautive (*). Donc pas de "problème de fond" autre que la fausseté de la preuve.
Par contre, un problème heuristique : l'existence de vols de grande taille (des séries de pairs-impairs où les impairs croissent) rend cette preuve inopérante, puisque de n on passe au plus à 3n+5. Elle ne sera pas rectifiable.

En tout cas, un essai assez différent de ce qu'on voit habituellement sur le sujet, même si depuis le temps, l'existence d'une démonstration avec des moyens élémentaires devient très improbable. Bravo Gravitoin !

Cordialement.

(*) si on arrivait à faire cette preuve, ce serait fini.

[Merlin95]

J'ai relu et effectivement tu tentes bien de démontrer toutes les hypothèses au rang (n+1).
Je te propose un schema de récurrence, en démontrant 3 récurrences, pour mieux comprendre ce qu'il se passe même si ca ne marchera pas dans cette tentative, ça permettra d'être plus rigoureux, car j'ai l'impression qu'on peut facilement faire un raisonnement cyclique entre les n pairs, n impairs, n+1 pair, n+1 impair...

Donc je te propose quelque chose de plus simple d'abord.
Récurrence 1 :
Soit n>1, supposons vraies les Hi suivantes :
H1 : Pn vraie tout entier entre 1 et n
H2 : Pn vraie pour tout entier entre (n+2) et (3n+5)
Alors il faut démontrer que ces propriétés sont vraies au rang (n+1), c'est-à-dire que la conjecture de Syracuse est vraie pour (3n+6), (3n+7), (3n+8)

Récurrence 2 :
Soit n pair alors supposons vraie l'H'1 suivante :
H'1 : Pn est vraie pour l’entier (6n+14)
Alors il faut montrer que la conjecture de Syracuse est vraie pour le nombre pair suivant (n+2), soit (6n+20)

Récurrence 3 :
Soit n impair alors supposons vraie l'H''1 suivante :
H''1 : Pn est vraie pour les entiers entre (6n+12) et (6n+16)

Alors il faut montrer que cette proprieté est vraie pour le nombre impair suivant (n+2), soit que la conjecture de Syracuse est vraie pour (6n+18), (6n+19), (6n+20), (6n+21), (6n+22).

Tu peux essayer de démontrer ces récurrences indépendamment (tu peux utiliser le résultat de ta récurrence 1 dans la 2 et la 3).

Si tu as réussi à prouver la récurrence 1 et la 2 tu peux les utiliser dans 3, ou si tu as réussi à prouver la récurrence 1 et la 3, tu peux les utiliser dans 2.

Si tu n'y arrives pas, je pense que la démo est surement fausse, car propice à un raisonnement cyclique difficile, en plus à identifier.

[gg0]

Merlin95,

le problème de ce qu'a fait Gravitoin n'est pas la forme de son hypothèse de récurrence, mais le fait qu'il a mal traduit P(n+1). Étant en terminale, il avait des doutes sur une hypothèse de récurrence construite ainsi, mais le problème n'était pas là. Et les cas pour n supérieur à n+1 étaient nécessaire à sa preuve fausse, les séparer n'apporte rien, ils n'ont plus d'intérêt.
Je me suis posé aussi la question de savoir si ces cas ne faussaient pas la récurrence, mais écrite comme je l'ai fait au message #20, elle est tout à fait correcte; et ce n'était qu'une réécriture de l'idée de Gravitoin.

Cordialement.

[Merlin95]

Oui mais je n'ai pas compris dans ce message si le P(n), défini au message #20 donc, permet de montrer la conjecture de Syracuse pour tout n ?

[MissJenny]

j'ai l'impression que ce genre d'approche est voué à l'échec, autrement dit que gravitoin ne pourra jamais réparer sa preuve. C'est parce que la suite peut atteindre des valeurs très grandes à partir d'un point de départ pas si grand, en tout cas, partant de n elle peut dépasser très largement les environs de 6*n. Or la preuve de gravitoin est basée sur le fait que lorsqu'on regarde le cas du nombre n+1, on ne rencontre que des nombres dont on sait déjà qu'ils conduisent à 1. On les rencontre à la première itération mais du coup à la seconde et ainsi de suite. A mon avis ça ne peut pas fonctionner.

[gg0]

Merlin95, le message #20 dit bien que la preuve de Gravitoin ne marche pas. Et que le défaut n'est pas dans la forme de la récurrence, mais dans le passage de P(n) à P(n+1). Je donne même une raison de l'impossibilité qu'une telle preuve puisse fonctionner. Et MissJenny confirme.
Si on était capable de démontrer P(n)==> p(n+1) on aurait bien une preuve par récurrence de la conjecture de Collatz. Mais avec des si ...

Cordialement.

[gravitoin]

Merci beaucoup pour vos réponses. J'y vois maintenant plus clair!! Effectivement MissJenny je ne pense pas que cette erreur soir réparable.
Passez une bonne journée.

[Liet Kynes]

Bonjour, perso je ne comprends pas dès ce stade; "Si n+1 est impair on le multiplie par 3 et on ajoute 1. On obtient donc 3n+4. Or
d’après l’hypothèse de récurrence, cet entier converge vers 1."

Comment est-il montré que 3n+4 converge vers 1 avec n impair ?

[gg0]

3n+4 est entre n+2 et 3n+5, donc ...

[Liet Kynes]

Ok, l'idée était-elle de chercher une sorte de boucle ?

[gg0]

Non. Pas de boucle dans la récurrence.