Khôlle : Pour les cancres

[Ben314]

...Par double inclusion ?

Oui, et, dans les deux cas, il faut évidement procéder par récurrence.

[benekire2]

Salut ben !!

D'accord, je dois donc faire des récurrences, ce que j'avais intuité même si ça me parrait vachement chaud de s'en sortir avec des récurrences.

Pour l'inclusion de "la suite" dans les premiers entre eux , il faut montrer que PGCD(x(n);x(n+1))=1 mettons que n soit impair alors n+1 est pair et alors x(n+1)=x((n+1)/2) et x(n)= x(n-1/2)+x(n+1/2) ainsi cela reviens à calculer PGCD(x(n-1/2);x(n+1/2)) et je vois pas comment faire ?

J'ai surement zappé quelque chose d'élémentaire je suppose ... :doh:

Merci !

[Ben314]

J'ai surement zappé quelque chose d'élémentaire je suppose ... :doh:

T'as p'têt être zappé le fait que tu est en train de faire une récurrence et donc que tu suppose que la propriété est vraie pour tout entier k<n...

[benekire2]

T'as p'têt être zappé le fait que tu est en train de faire une récurrence et donc que tu suppose que la propriété est vraie pour tout entier k<n...

Non , pas du tout ... :zen:
Je vais me cacher !

[Ben314]

Pour la réciproque, il faut aussi raisonner par récurrence.
Sauf que, comme on manipule des couples (p,q) d'entiers non nuls premiers entre eux, il faut trouver sur quoi faire la récurence.
Indic (blanc) :
On peut par exemple fair la récurrence sur p+q :
L'amorce consiste à vérifier que, si p+q=2 alors (p,q) fait parti de la liste.
Ensuite, on suppose que c'est O.K. pour tout les (p,q) tels que p+q<s et on montre que c'est aussi O.K. pour un couple (p,q) tel que p+q=s.


P.S. Je sais pas si la question ne sous entend pas aussi qu'il faut montrer l'unicité du couple, c'est à dire que, si p et q sont premiers entre eux, il existe un unique n tel que xn=p et x(n+1)=q.

[benekire2]

Merci ben :id:

Juste un truc, pour l'initialisation c'est ok, mais pour l'hérédité je vois pas trop trop comment procéder, faut que je fasse comment ? x(n)+x(n+1)=x(n-1/2)x(n/2)+x(n+1/2) et après ? C'est chaud d'utiliser les hypothèses ... Merci :zen:

[Doraki]

x(n)+x(n+1)=x(n-1/2)+x(n/2)+x(n+1/2) et après ?

Je sais pas où t'es allé chercher ça mais entre (n-1)/2, n/2, et (n+1)/2, je doute qu'il n'y ait que des entiers.

[benekire2]

Je sais pas où t'es allé chercher ça mais entre (n-1)/2, n/2, et (n+1)/2, je doute qu'il n'y ait que des entiers.

J'ai oublié les parenthèses, c'est x(n)+x(n+1)=x((n-1)/2)+x(n/2)+x((n+1)/2) mais si non c'est ça.

[Ben314]

J'ai oublié les parenthèses, c'est x(n)+x(n+1)=x((n-1)/2)+x(n/2)+x((n+1)/2) mais si non c'est ça.

Relit (calmement...) le post de Doraki qui te dit que...

[benekire2]

oui je me suis planté, si n est impair alors x(n)+x(n+1)=x(n)+x((n+1)/2)=2 x((n+1)/2)+x((n-1)/2) et si n est pair alors x(n)+x(n+1)=2 x(n/2)+x(n/2 +1)

normalement là c'est bon. Et donc j'ai

2 x(n/2)+x(n/2 +1)=s Évaluons PGCD(2 x(n/2) ; x(n/2 +1)) Or PGCD(x(n/2) ; x(n/2 +1)) donc le seul diviseur commun possible pour 2 x(n/2) et x(n/2 +1) est 2 .

Le problème c'est que les deux nombres ne sont pas encore premiers entre eux, faudrait montrer que c'est pas possible que 2| 2x(n/2) et x(n/2+1) mais je bloque

[Ben314]

Je comprend pas pourquoi tu ajoute les deux...
Si n est impair alors et, comme n+1 est pair, .
Donc

[benekire2]

= ...=1 ok

Si j'ai mis des 2 c'est que ... j'ai ajouté, alors que ici on en a pas besoin en fait ...


Merci beaucoup à toi Ben ! :zen:
Bonne soirée ( je vais me coucher )

PS: Après relecture, je voit pas ou c'est qu'on a prouvé que p et q sont consécutifs dans la suite ....

[Ben314]

Ce "morceau" de preuve là fait parti de la preuve pour montrer que pour tout n xn et x(n+1) sont premier entre eux (il faut aussi traiter le cas n pair qui est quasi identique).

Pour la réciproque, aprés avoir fait l'amorce (triviale), tu part d'un couple (p,q) d'entiers (>0) premier entre eux et tu suppose (hypothése de récurence) que pour tout couple (p',q') d'entiers (>0) premier entre eux tels que p'+q'<p+q, il existe un entier m tel que xm=p' et x(m+1)=q'.
Il faut que tu trouve un entier n tel que xn=p et x(n+1)=q.
(il y a de nouveau deux cas à traiter selon que...)

[benekire2]

donc en gros j'ai fais deux fois la même preuve ... parce que quand tu me demandais pourquoi j'avais des 2 ; c'est que j'avais sommer pour tenter une preuve sur la réciproque ..
Donc il existe n tel que x(n)+x(n+1)=p+q c'est a dire avec n impair (mettons) :
x((n-1)/2)+2x((n+1)/2)=p+q c'est de là que vient la somme et c'est aussi là que je ne peut pas avancer depuis tout à l'heure !

[Ben314]

Pour la réciproque, aprés avoir fait l'amorce (triviale), tu part d'un couple (p,q) d'entiers (>0) premier entre eux et tu suppose (hypothése de récurence) que pour tout couple (p',q') d'entiers (>0) premier entre eux tels que p'+q'<p+q, il existe un entier m tel que xm=p' et x(m+1)=q'.
Il faut que tu trouve un entier n tel que xn=p et x(n+1)=q.

Deux cas possibles :
1) Est il possible que avec n pair, c'est à dire que ?
Pour que ce soit le cas, il faut (et il suffit) que et que . Un tel n (pair) existe-t-il ?
2) Est il possible que avec n impair, c'est à dire que...

[benekire2]

(p,q)=( x(n) , x(n+1) ) avec n impair donc (p,q)=(x((n-1)/2)+x((n+1)/2),x((n+1)/2))

donc ssi q=x((n+1)/2) et p-q=x((n-1)/2)


C'est possible qu'ils existent puisque pgcd(x((n-1)/2),x((n+1)/2))=1
mais par contre j'ai aucune méthode pour prouver l'existence de ce n ... et j'utilise toujours pas les hypothèses de récurrence . Je ne vois toujours rien , désolé :mur:

[Ben314]

1) Est il possible que avec n pair, c'est à dire que ?
Pour que ce soit le cas, il faut (et il suffit) que et que .
Or, si q>p alors (p,q-p) est un couple d'entiers (>0) premiers entre eux (vu que p et q le sont) et, évidement, p+(q-p)<p+q.
Donc, par hypothèse de récurrence, il existe un entier m tel que et que .
Conclusion : n=2m donne le résultat.

Le deuxième cas (n impair) va, comme par hasard, correspondre au cas où q<p.

[benekire2]

Merci beaucoup ben !!

Le pire dans tout ça c'est quej'avais écrit cela et c'était juste, sauf que mon cerveau a voulu me faire croire que p+(q-p)=p+q et qu'on nee peut donc pas utiliser les hypothèses ....

Merci encore !