Récurrence vicieuse

**doryphore** · 08/08/2004, 20h52

Voici une tentative illicite pour démontrer par récurrence que pour n entiers quelconques $\text{[math]}$ il existe un unique entier naturel d tel que $\text{[math]}$ .

Ecriture de l'hypothèse à démontrer:

$\text{[math]}$

Au rang n=1, on a naturellement $\text{[math]}$
Montrons l'unicité:
Si $\text{[math]}$ , donc dans $\text{[math]}$

On suppose que $\text{[math]}$

$\text{[math]}$ par hypothèse de récurrence. (p=n)

De même, $\text{[math]}$

Par conséquent la proposition est démontrée pour tout n.

Trouver la faille dans la démonstration. Cracks s'abstenir au moins dans un premier temps.

inviteca3a9be7 · 08/08/2004, 21h23

J'ai dans l'idée que le deuxième d (d° ?), il dépend un peu trop de la variable libre a(n+1) ....

**doryphore** · 08/08/2004, 21h49

C'est d', LaTex fait les primes à hauteur des genous, on dirait.
M'enfin sans lui, je n'aurais pas pu proposer l'exo.

Qu'est-ce que tu veux dire par d' dépend trop de $\text{[math]}$ , je n'ai fait que réutiliser l'Hypothèse de récurrence avec p=2.

Je n'ai pas bien compris si tu as ou non la solution, mais si tu l'as, attends un peu, il m' a fallu 1 heure pour taper le message.

invite51f4efbf · 09/08/2004, 08h31

Envoyé par doryphore

Voici une tentative illicite pour démontrer par récurrence que pour n entiers quelconques $\text{[math]}$ il existe un unique entier naturel d tel que $\text{[math]}$ .

Je ne sais pas pour la preuve (j'en suis encore au café, je ne l'ai donc pas lue

), mais ça ne me parait pas faux

. C'est juste le fait que $\text{[math]}$ est principal non ?

A voir en vidéo sur Futura · Aujourd'hui

**doryphore** · 09/08/2004, 10h19

Oui, quand on utilise comme outils les idéaux cette preuve est complètement obsolète.
Par contre la preuve est fausse, j'en suis assez persuadé et je pense savoir pourquoi.

invite51f4efbf · 09/08/2004, 11h57

Envoyé par doryphore

Oui, quand on utilise comme outils les idéaux cette preuve est complètement obsolète

En fait il n'y a même pas besoin d'idéaux, il suffit de montrer que les sous-groupes propres de $\text{[math]}$ sont de la forme $\text{[math]}$ (et c'est assez facile - ça vient de la division avec reste).

Envoyé par doryphore

Par contre la preuve est fausse, j'en suis assez persuadé et je pense savoir pourquoi.

Possible : je ne l'ai toujours pas lue (mais je vais m'y mettre quand j'aurais fini la patachiée de trucs que j'ai à faire !) D'ici là je pense que l'un d'entre vous aura trouvé

Amicalement,
Stephen.

inviteca3a9be7 · 09/08/2004, 19h29

Envoyé par doryphore

Qu'est-ce que tu veux dire par d' dépend trop de $\text{[math]}$ , je n'ai fait que réutiliser l'Hypothèse de récurrence avec p=2.

Tu as vraiment vraiment le droit utiliser a(n+1)

? C'est une variable que apparaît dans un quantificateur, c'est pas une constante ou une donnée ....

**doryphore** · 09/08/2004, 20h14

Envoyé par µµtt

Tu as vraiment vraiment le droit utiliser a(n+1)

? C'est une variable que apparaît dans un quantificateur, c'est pas une constante ou une donnée ....

Je n'oserais pas être trop affirmatif, mais je crois bien que tu fais fausse route $\text{[math]}$ .

J'ai supposé que pour toute famille de n éléments de $\text{[math]}$ , il existait un unique d naturel tel que $\text{[math]}$ . (d est un pgcd de la famille)

Maintenant, je vérifie que c'est vrai au rang n+1, donc je prends à présent une famille de n+1 entiers et je cherche à démontrer l'existence et l'unicité d'un pcgd positif de cette famille. Pour cela j'utilise l'hypothèse de récurrence qui est une hypothèse sur le nombre d'éléments de ma famille à deux reprises.
Rien de choquant à première vue.

La vérité est ailleurs...

**doryphore** · 09/08/2004, 21h38

Envoyé par Stephen

En fait il n'y a même pas besoin d'idéaux, il suffit de montrer que les sous-groupes propres de $\text{[math]}$ sont de la forme $\text{[math]}$ (et c'est assez facile - ça vient de la division avec reste).

Ah oui, tiens. Mais je pense que toute démonstration de l'existence et de l'unicité du pgcd se ramène à cette division euclidienne.

Alors que ma démonstration semble être en mesure de se passer de cet argument.

Je dis ça au cas où vous croiriez que ma démonstration est bonne.

invite74de5f91 · 10/08/2004, 07h40

Salut à tous, voilà je pense que l'erreur se situe ici :

Envoyé par doryphore

$\text{[math]}$ par hypothèse de récurrence. (p=n)

A mon avis, "l'erreur" vient de la manipulation des kZ, comme s'il s'agissait d'entiers (alors que ce sont des ensembles d'entiers).
Ce qui est écrit ici est équivalent à la formule :
$\text{[math]}$ (1)

Alors que l'hypothèse de récurrence ne donne que :
$\text{[math]}$ (2)

Et (2) n'implique pas (1) à cause de l'unicité imposée sur d.

**doryphore** · 10/08/2004, 10h14

Raté !!!

Le couple $\text{[math]}$ que tu obtiens en (2) grace à l'hypothèse de récurrence est exactement le couple $\text{[math]}$ que tu cherches justement à cause de l'unicité de d.

C'est encore plus vicieux que cela. Si personne n'a trouvé ce soir, je donne un indice décisif.

invite6f044255 · 10/08/2004, 10h26

Envoyé par doryphore

Montrons l'unicité:
Si $\text{[math]}$ , donc dans $\text{[math]}$

L'erreur est là, non?

d=1 ça marche bien aussi, quelque soit a1?

Je vérifie et je reviens.

invite6f044255 · 10/08/2004, 10h27

Oui c'est ça!!

**doryphore** · 10/08/2004, 10h41

Et non,

On a toujours $\text{[math]}$ , mais si $\text{[math]}$ , on a pas $\text{[math]}$ , en effet dans ce cas $\text{[math]}$

Bien tenté quand même.

invite6f044255 · 10/08/2004, 14h06

je suis peut-être têtu, mais:

l'hypothèse de récurrence au rang 1 est

"pour a1 entier, il existe un unique d tel que pour tout relatif y, il existe un relatif x tel que a1*y=d*x "

si d=1, il suffit de prendre x=a1*y et ça marche, non?

donc si a1 différent de 1, pas unicité...
ou alors je suis à côté de la plaque....

invite6f044255 · 10/08/2004, 14h16

Et puis ça:

Envoyé par doryphore

De même, $\text{[math]}$

C'est l'hypothèse de récurrence au rang 2!! On n'a pas le droit de l'utiliser!!

**doryphore** · 10/08/2004, 19h08

Envoyé par ixi

si d=1, il suffit de prendre x=a1*y et ça marche, non?

Initialisation: tu regardes ce qui se passe quand n=1.
Soit a un entier quelconque. Pour te faire plaisir, prenons a=1.
Existe-t-il un unique d entier positif tel que $\text{[math]}$

Oui, d=1 convient. Est-il unique ?
A toi de voir, mais n'oublie pas que c'est pour tout y.

C'est d qui se détermine en fonction de ta famille d'entiers et non le contraire. Ton explication n'est donc pas très convaincante.

C'est l'hypothèse de récurrence au rang 2!! On n'a pas le droit de l'utiliser!!

YES!!!

L'hérédité fonctionne parfaitement pour passer de n à n+1 tant que n est supérieur ou égal à 2.

Le rang 1 était vérifié, et on pouvait passer de n'importe quel rang au suivant sauf du rang 1 au rang 2 car la vérification de l'hérédité nécessite a priori la validité au rang 2. Donc tout se cassait la g...

Donc pour compléter cette démonstration, il faut démontrer qu'elle est vraie au rang 2.
Ce qui est nettement moins trivial. On peut utiliser par exemple l'algorithme d'Euclide pour déterminer d, d'où les divisions euclidiennes citées plus haut.

invite6f044255 · 10/08/2004, 20h03

Ouais, ouais, et pourtant je suis nul en maths!!

Mais mon intellect supra-exceptionnel vous a encore tous surpassé. Mouahahahahaha!!!!!

j'ai gagné quoi? dis doryphore, j'ai gagné quoi?

**doryphore** · 10/08/2004, 20h28

Tu as le droit de démontrer que que la proposition est vraie au rang 2.

Chouette, hein !!!

invite74de5f91 · 10/08/2004, 20h32

Bien vu pour l'hypothèse de rang 2, effectivement on ne peut pas l'utiliser... Mais je maintiens ma remarque, la démonstration reste fausse même si on démontre le rang 2, à cause de la différence entre (1) et (2).

Envoyé par doryphore

Le couple $\text{[math]}$ que tu obtiens en (2) grace à l'hypothèse de récurrence est exactement le couple $\text{[math]}$ que tu cherches justement à cause de l'unicité de d.

Mmh, je n'en suis pas si sûr... Es-tu sûr que tu peux démontrer rigoureusement (1) à partir de (2) ?. L'unicité ne concerne pas y1 ou y2, mais d. Et dans (1) c'est cette unicité sur d qu'il faut démontrer. Un bref calcul sur un exemple où $\text{[math]}$ me montre d'ailleurs que (1) est fausse.

Par l'absurde, supposons que (1) soit vraie.
rappel : (1) est $\text{[math]}$

Prenons alors $\text{[math]}$ tel que $\text{[math]}$ . Ainsi, on a :
(*) $\text{[math]}$
et d est l'unique entier vérifiant (*).
On peut alors en déduire :
$\text{[math]}$
On a alors :
(**) $\text{[math]}$
(j'ai posé $\text{[math]}$ et $\text{[math]}$ )
D'après (*) et (**), par unicité sur d, on a alors d = d+1. Ce qui est impossible.
Donc (1) est fausse.

**doryphore** · 10/08/2004, 20h56

Tu as parfaitement raison.

Je n'ai pas le droit de dire que le d qui vérifie:
$\text{[math]}$ est unique.

Je m'excuse de ne pas avoir prêter suffisammant attention à ce que tu me disais.

Heureusement, cette unicité n'est pas utile à la démonstration.
Seule compte l'existence du d.

Nous avons donc deux gagnants.

invite6f044255 · 10/08/2004, 21h01

La prochaine fois, je posterai mes DM de maths, ya pleins de démonstrations foireuses dedans aussi....

invite6f044255 · 10/08/2004, 21h16

Après réflexion, je ne crois pas que la remarque d'aleph0 vaille, je m'explique:

y2 n'est autre que x(n+1) dans la relation (1).
C'est en le renommant seulement à droite que nait la confusion.

Pour qu'on puisse dire qu'on a un "d", il faut que ce soit x(n+1) à droite de l'égalité, or z2 n'est pas x(n+1)....

En effet, dans (1) en soustrayant

$\text{[math]}$
on retrouve l'hypothèse de récurrence au rang n.
Mais pas dans l'expression avec z1 et z2.

Tu trouves un d (en l'occurrence d+1) certes, mais il ne vérifie pas l'hypothèse de récurrence au rang n.

**doryphore** · 10/08/2004, 21h45

En fait, à la place d'écrire:
$\text{[math]}$ , j'aurais pu écrire:

$\text{[math]}$

Il y a une petite nuance entre les deux que je n'avais pas perçue tout de suite.

invite74de5f91 · 10/08/2004, 22h14

Envoyé par ixi

y2 n'est autre que x(n+1) dans la relation (1).
C'est en le renommant seulement à droite que nait la confusion.

Ce que j'ai ecrit, c'est simplement une démonstration que (1) est fausse, indépendamment de l'hypothèse de récurrence. J'ai donnée cette preuve, pour mettre en evidence que (2)(qui est l'hypothèse de récurrence pour p=n) et (1) ne disent pas du tout la même chose. (ceci se voit bien sur la quantification existentielle sur y1 et y2)
Je ne vois pas pourquoi, dans (1), y2 est égal à $\text{[math]}$

)

Envoyé par doryphore

Heureusement, cette unicité n'est pas utile à la démonstration.
Seule compte l'existence du d.

Oui, c'est vrai, si on souhaite juste démontrer :
Pour tout $\text{[math]}$ il existe au moins un entier naturel d tel que $\text{[math]}$ (on enlève l'unicité)
Alors la démonstration marche (on enlève les unicité sur d pour toutes les formules).
Tu aurais donc pu ecrire :
$\text{[math]}$
et en déduire :
$\text{[math]}$
puis utiliser l'hypothèse au rang 2(préalablement démontrée) (sans unicité non plus) et obtenir le rang n+1 :
$\text{[math]}$
En revanche, je ne saurais pas démontrer "élémentairement" :
Pour tout $\text{[math]}$ il existe un unique entier naturel d tel que $\text{[math]}$

invite6f044255 · 10/08/2004, 23h01

Ca y est, j'ai pigé ton truc aleph-0!!
je suis désolé, j'ai mis le temps....

mais ça y est j'ai compris et je suis d'accord!!

La meilleure façon de résumer ce fil est
.............................. .............................. .............................. ........................Vive la physique!!

invite74de5f91 · 12/08/2004, 05h01

Envoyé par doryphore

En fait, à la place d'écrire:
$\text{[math]}$ , j'aurais pu écrire:
$\text{[math]}$
Il y a une petite nuance entre les deux que je n'avais pas perçue tout de suite.

Oui en fait comme tu le dis doryphore ça marche bien même avec l'unicité...

C'était juste une erreur d'écriture qui ne porte pas à conséquence sur la suite du raisonnement.
Bien vu comme récurrence vicieuse !

tu as imaginé le piège ou tu l'as vu quelque part (devoirs, kholle ?) (sans être indiscret)

**doryphore** · 12/08/2004, 06h44

En fait, c'est en tentant de faire cette démonstration que j'ai produit celle-ci.
J'ai tout de suite senti qu'il y avait un malaise, que la démonstration était un peu creuse. Et surtout, elle n'arrivait pas à me convaincre que c'était vrai au rang 2.
J'ai comaté pendant un bon quart d'heure avant de trouver la faille du raisonnement.
Comme l'erreur était relativement subtile, je l'ai soumis ici, en espérant que cela intéresse certains d'entre vous.

Ta remarque aura permis de rendre encore plus rigoureuse cette démonstration.
Merci.

invite3200dca9 · 14/08/2004, 09h56

Il est fort ce dory-phore !!

Récurrence vicieuse

Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Re : Récurrence vicieuse

Discussions similaires

TS Recurrence

récurrence TS

récurrence

récurrence

Téléviseur Philips (panne vicieuse)