Le principe de récurrence est l’un des outils les plus puissants du raisonnement mathématique. Il consiste, pour établir une propriété générale du type « pour tout \(n, P(n)\) », à prouver deux affirmations :
(i) \(P(0)\) est vrai
(ii) si \(P(n)\) est vrai pour \(n = 0, 1, \ldots, k\), alors \(P(k +1)\) est vrai.
Dans un raisonnement par récurrence, malheureusement l’intuition est un peu perdue, aussi des erreurs deviennent possibles. Voici un exemple de raisonnement par récurrence conduisant à une
absurdité.
Nous allons démontrer qu’en mathématiques rien ne bouge, plus précisément, nous allons établir que toutes les fonctions \(x \to x^n\) (\(n\) un entier fixé) sont des fonctions constantes.
(i) C’est vrai pour \(n = 0\) car \(x^0 = 1\) (par convention) et que la dérivée d’une constante est la fonction nulle.
(ii) Supposons que c’est vrai pour \(n = 0, 1, \ldots, k\), c’est-à-dire que la dérivée de la fonction \(x \to x^n\) est nulle :
\[(x^n)’ = 0 \text{ pour } n = 0, 1, \ldots, k.\]
Utilisons maintenant la formule de dérivation d’un produit (\(uv)’ = u’v+ uv’\). On a : \[(x^{k+1})’ = (x \cdot x^k)’ = x‘ \cdot x^k + x \cdot (x^k)’\]
On obtient 0 car, d’après l’hypothèse de récurrence, on a \(x’ = (x^1)’ = 0\) (on utilise l’hypothèse avec \(n = 1)\) et \((x^k)’ = 0\) (on utilise l’hypothèse avec \(n = k)\).
Nous avons donc \((x^{k +1})’ = 0\), ce que nous souhaitions. Qu’est-ce qui cloche ?
Solution
Lorsque \(k = 0\), l’hypothèse de récurrence donne uniquement \((x^0)’ = 0\) et non pas comme le raisonnement l’utilise que
\[(x^0)’ = 0 \text{ et }(x^1)’ = 0\]
Le passage de \(k\) à \(k + 1\) fonctionne donc bien pour aller de 1 à 2, 2 à 3, de 3 à 4, etc., mais ne marche pas pour aller de 0 à 1. Le seul fait qu’une étape ne puisse fonctionner rend évidemment la conclusion fausse…, ce que nous savions par avance, mais dont il fallait comprendre la raison.
La confusion provient de la notation \(n = 0, 1, \ldots, k\) qui laisse croire qu’à chaque étape on a au moins \(P(0)\) et \(P(1)\) vrais, alors qu’en fait lorsque \(k = 0\), on a seulement \(P(0)\).
