Récurrence vicieuse

ixi · 10/08/2004 - 14h16

Et puis ça:

Envoyé par doryphore

De même, $\exists! d' \in \mathbb{N} \ d\mathbb{Z}+a_{n+1}\mathbb{Z}= d'\mathbb{Z}$

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 $\forall y \in \mathbb{Z} \ \exists x \ y=dx$

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.

ixi · 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 !!!

Aleph-0 · 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 $(x,x_{n+1})$ que tu obtiens en (2) grace à l'hypothèse de récurrence est exactement le couple $(y_1,y_2)$ 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ù $a_{n+1} =1$ me montre d'ailleurs que (1) est fausse.

Par l'absurde, supposons que (1) soit vraie.
rappel : (1) est $\forall(a_1,...,a_{n+1}) \in \mathbb{Z}^{n+1} \ \exists! d \in \mathbb{N} \ \forall(x_1,...,x_{n+1}) \in \mathbb{Z}^{n+1} \ \exists y_1, y_2 \in \mathbb{Z} \ \sum_{i=1}^{n+1}a_{i}x_i=dy_1 +a_{n+1}y_2$

Prenons alors $(a_1,...,a_{n+1})$ tel que $a_{n+1} = 1$ . Ainsi, on a :
(*) $\forall(x_1,...,x_{n+1}) \in \mathbb{Z}^{n+1} \ \exists y_1, y_2 \in \mathbb{Z} \ \sum_{i=1}^{n+1}a_{i}x_i=dy_1 +y_2$
et d est l'unique entier vérifiant (*).
On peut alors en déduire :
$\forall(x_1,...,x_{n+1}) \in \mathbb{Z}^{n+1} \ \exists y_1, y_2 \in \mathbb{Z} \ \sum_{i=1}^{n+1}a_{i}x_i=(d+1) y_1 - y_1 +y_2$
On a alors :
(**) $\forall(x_1,...,x_{n+1}) \in \mathbb{Z}^{n+1} \ \exists z_1, z_2 \in \mathbb{Z} \ \sum_{i=1}^{n+1}a_{i}x_i=(d+1) z_1 + z_2$
(j'ai posé $z_1 = y_1$ et $z_2 = -y_1 + y_2$ )
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:
$\sum_{i=1}^{n+1}a_i \mathbb{Z}=d\mathbb{Z}+a_{n+1} \mathbb{Z}$ 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.

ixi · 10/08/2004 - 21h01

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

ixi · 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

$a_{n+1}x_{n+1}$
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:
$\exists!d\in\mathbb{N} \ \sum_{i=1}^{n+1}a_i\mathbb{Z}= d\mathbb{Z}+a_{n+1}\mathbb{Z}$ , j'aurais pu écrire:

$\exists! d\in\mathbb{N} \ \forall(x_1,...,x_{n+1})\in \mathbb{Z}^{n+1} \ \exists x \in \mathbb{Z} \ \sum_{i=1}^{n+1}a_i x_i=dx+a_{n+1}x_{n+1}$

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

Aleph-0 · 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 à $x_{n+1}$

)

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 $a_{1},a_{2},...,a_{n}$ il existe au moins un entier naturel d tel que $\sum_{i=1}^{n}a_{i}\mathbb{Z}= d\mathbb{Z}$ (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 :
$\exists d\in\mathbb{N} \ \forall(x_1,...,x_{n+1})\in \mathbb{Z}^{n+1} \ \exists x \in \mathbb{Z} \ \sum_{i=1}^{n+1}a_i x_i=dx+a_{n+1}x_{n+1}$
et en déduire :
$\exists d\in\mathbb{N} \ \sum_{i=1}^{n+1}a_i\mathbb{Z}= d\mathbb{Z}+a_{n+1}\mathbb{Z}$
puis utiliser l'hypothèse au rang 2(préalablement démontrée) (sans unicité non plus) et obtenir le rang n+1 :
$\exists d^'\in\mathbb{N} \ \sum_{i=1}^{n+1}a_i\mathbb{Z}= d^'\mathbb{Z}$
En revanche, je ne saurais pas démontrer "élémentairement" :
Pour tout $a_{1},a_{2},...,a_{n}$ il existe un unique entier naturel d tel que $\sum_{i=1}^{n}a_{i}\mathbb{Z}= d\mathbb{Z}$

ixi · 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!!

Aleph-0 · 12/08/2004 - 05h01

Envoyé par doryphore

En fait, à la place d'écrire:
$\exists!d\in\mathbb{N} \ \sum_{i=1}^{n+1}a_i\mathbb{Z}= d\mathbb{Z}+a_{n+1}\mathbb{Z}$ , j'aurais pu écrire:
$\exists! d\in\mathbb{N} \ \forall(x_1,...,x_{n+1})\in \mathbb{Z}^{n+1} \ \exists x \in \mathbb{Z} \ \sum_{i=1}^{n+1}a_i x_i=dx+a_{n+1}x_{n+1}$
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.

Rasmus · 14/08/2004 - 09h56

Il est fort ce dory-phore !!

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

Sur le même sujet

Discussions similaires

TS Recurrence

récurrence TS

récurrence

récurrence

Téléviseur Philips (panne vicieuse)

Les tags pour cette discussion