Trouver et nommer l'erreur de la démonstration suivante, qui prétend établir que pour tout n≥1, n boules quelconques sont toutes de la même couleur.Copie : « Pour
n≥1, notons
P(n) : tout ensemble de
n boules ne contient que des boules d'une même couleur.
Initialisation : un ensemble d'une seule boule ne contient qu'une couleur, donc
P(1) est vraie.
Hérédité : soit
n≥1 tel que
P(n) soit vraie, et soit un ensemble de
n+1 boules
b1,…,bn+1. D'après
P(n), les boules
b1,…,bn ont la même couleur ; d'après
P(n) encore, les boules
b2,…,bn+1 aussi. La boule
b2 appartient aux deux groupes, donc les
n+1 boules ont la couleur de
b2, et
P(n+1) est vraie.
Conclusion : par récurrence,
P(n) est vraie pour tout
n≥1. »
Correction.
L'énoncé est faux : une boule rouge et une boule bleue forment un ensemble de deux boules de couleurs différentes, donc
P(2) est fausse. La démonstration contient donc au moins une erreur.
L'initialisation est juste :
P(1) est vraie.
Comme
P(1) est vraie et
P(2) fausse, l'hérédité ne peut pas être valable pour
n=1 : c'est là qu'il faut chercher.
Relisons l'hérédité avec
n=1 : l'ensemble est
{b1,b2}, le premier groupe est
{b1} et le second est
{b2}.
L'erreur est la phrase « la boule
b2 appartient aux deux groupes » : pour
n=1, le premier groupe se réduit à
b1, les deux groupes n'ont aucune boule commune, et rien ne relie la couleur de
b1 à celle de
b2.
Nom de l'erreur : l'hérédité s'appuie sur un fait vrai seulement pour
n≥2, les deux groupes partageant alors les boules
b2,…,bn, et l'affirme pour tout
n≥1. C'est une erreur de logique sur le domaine de la variable
n, qu'une relecture menée avec un
n abstrait laisse facilement passer, et qu'on voit aussitôt en écrivant
n=1.
Ce que le texte démontre réellement : que
P(1) est vraie, et que pour tout
n≥2, si
P(n) est vraie, alors
P(n+1) l'est. Ces deux faits ne s'enchaînent pas, faute du maillon qui mènerait de
P(1) à
P(2) : aucun
P(n) avec
n≥2 n'en découle.
À retenir : quand une récurrence prouve un énoncé faux, on relit l'hérédité en y écrivant la plus petite valeur de
n en chiffres.