Récurrence fausse?

Question

Le raisonnement suivant est faux, mais je ne sais pas vraiment où est l'erreur, pourriez-vous m'aider?

Je me propose de démontrer par récurrence la proposition suivante P(n) : si une trousse contient n crayons, alors ils sont tous de la même couleur.

L'initialisation est évidente : P(1) vraie.
Supposons P(n) :dans la trousse il y a n crayons de la même couleur, disons arbitrairement bleus. Le (n+1)e crayon est à l'extérieur de la trousse. J'enlève un crayon(bleu) de la trousse rajoute dans la trousse le (n+1)e crayon : par hypothèse de récurrence, tous les n crayons dans la trousse sont de la même couleur, donc bleus. Il ne reste plus qu'à rajouter le crayon bleu que j'avais enlevé précédemment : j'ai donc maintenant dans ma trousse (n+1) crayons bleus. Donc P(n+1) est vraie.

Evidemment ce raisonnement est faux (il suffit de prendre sa trousse et de regarder...). J'ai peut être une idée de l'erreur mais je ne suis pas sûr. Pourriez-vous m'aider à trouver l'erreur svp?

PS : pour répondre à Lenny, on a bien n+1-1=n car lorsque j'utilise l'hypothèse de récurrence, je raisonne en termes de crayons et non en termes de crayons bleus.

Answer 1

Déjà il faut rédiger un peu mieux la fausse démonstration. Ici l'hypothèse de récurrence n'est pas la bonne. Je reprends donc :

Montrons que si une trousse contient n crayons, alors ils sont tous de la même couleur.
P(n) : "Si une trousse contient n crayons, alors ils sont tous de la même couleur.'"
P(0) et P(1) sont évidemment vrais.

Supposons P(n) et montrons P(n+1). Une trousse contient n+1 crayons ; j'en enlève un de la trousse. Il en reste n dedans donc par hypothèse de récurrence, ils sont tous de la même couleur.
Je rajoute maintenant le crayon enlevé ; s'il est de la même couleur que les autres c'est fini. Sinon j'en enlève un autre, on a par hypothèse de récurrence que tous sont de la même couleur.
Parmi tous ces crayons un est de la même couleur que les deux successivement enlevés (puisqu'il a participé aux deux vérifications). Donc ils sont tous de la même couleur.

L'erreur n'est pas évidente et beaucoup d'élèves font des erreurs de ce type.
L'initialisation est correcte mais l'hérédité est fausse pour le cas n = 2. En effet, quand on enlève un crayon, on dit juste que celui qui reste est de la même couleur que lui (trivial). Ensuite on permute et on dit que l'autre est de la même couleur que lui (trivial). Mais ici il n'y a pas de troisième crayon qui permette de dire que ces deux mêmes couleurs sont les mêmes.

A noter que l'hérédité est vraie à partir de n = 3. L'hypothèse de récurrence est bien : "Si j'ai n crayons dans la trousse ils sont de la même couleur" et non "J'ai n crayons de même couleur dans une trousse" qui est un juste un cas particulier.

Answer 2

Dans ton cas n + 1 -1 n'est pas égal à n mais à m, où
m= (n-1) crayons bleus + 1 crayon d'une couleur inconnue.
Quand j'étais gamine, les instits appelaient ça, en termes plus imagés, additionner les carottes et les poireaux. Ça fait de la soupe, mais pas un plat de carottes ou de poireaux. Même si tu as le m^me poids au bout.
:-)

Answer 3

L'erreur est dans le "donc bleus". C'est à dire que tu supposes déjà que n+1>2. Effectivement tu as démontré que si on a p(n), alors on a p(n+1), à condition que n+1 soit supérieur à 3. Pour n=1 la démonstration ne fonctionne pas, et la récurrence est tuée dans l'oeuf.

Answer 4

A mon avis, c'est P(n) qui est bancal dans le raisonnement...
Parce qu'en fait si on reprend bien le raisonnement, la correcte hypothèse de récurrence est:
Q(n): n crayons de la même couleur sont de la même couleur (ce qui est évidemment vrai
Or dans le raisonnement, on a pas pris ce Q(n) comme hypothèse de récurrence, mais au lieu de prouver Q(n+1), on a prouvé P(n+1)=les (n+1) crayons d'une trousse sont de la même couleur
Ce qui n'est pas toujours vrai!

Answer 5

Ton itération est fausse et comme tu n'utilises qu'un peusdo résonnement mathématiques tu ne peux pas avoir quelque hose de correct.

Answer 6

Ffffouuuuuuuuu

Answer 7

Salut