La méthode de preuve par récurrence (appelée aussi preuve par induction) est une technique de démonstration qui, quand elle s'applique, permet de démontrer une infinité d'affirmations en seulement deux étapes.
Supposons que l'on définisse, pour chaque entier \(n\geqslant 1\), une certaine propriété \(\mathcal{P}(n)\). Pour chaque \(n\), \(\mathcal{P}(n)\) est soit vraie, soit fausse.
Exemple: Soit \(\mathcal{P}(n)=\)''le nombre entier \(n\) est divisible par \(2\)''. Alors \(\mathcal{P}(1)\) est fausse, \(\mathcal{P}(2)\) est vraie, \(\mathcal{P}(3)\) est fausse, etc. Donc on peut tout de suite résoudre tous les cas: \(\mathcal{P}(n)\) est vraie si \(n\) est pair, fausse si \(n\) est impair.
Supposons ensuite
que dans un cas concret, on ait des raisons de penser
que toutes les propriétés sont vraies:
\(\mathcal{P}(1)\) est vraie,
\(\mathcal{P}(2)\) est vraie,
\(\mathcal{P}(3)\) est vraie, etc.
Si ces propriétés \(\mathcal{P}(n)\) n'ont rien à voir les unes avec les autres, on
n'a d'autre alternative que de les vérifier les unes après les autres.
Exemple: Supposons qu'un certain univers soit infini, et contienne une infinité de galaxies. Soit \(\mathcal{P}(n)\) la propriété ''il existe, dans cet univers, une galaxie dans laquelle on peut trouver exactement \(n\) planètes sur lesquelles on trouve la vie''. Dans ce cas, si on fixe un \(n\) et qu'on se pose la question de savoir si \(\mathcal{P}(n)\) est vraie ou fausse, on n'a qu'un seul moyen: parcourir tout l'univers jusqu'à trouver une galaxie contenant exactement \(n\) planètes sur lesquelles on trouve la vie. Il n'y a aucune corrélation entre les propriétés \(\mathcal{P}(n)\) pour des \(n\) différents. Par exemple, savoir que \(\mathcal{P}(n-1)\) et \(\mathcal{P}(n+1)\) son vraies n'implique pas forcément que \(\mathcal{P}(n)\) soit vraie aussi.
Mais, si on a de la chance, il se pourrait qu'il existe une relation entre ces propriétés qui permette de gagner du temps. Plus particulièrement, il se pourrait qu'on remarque qu'à chaque fois qu'une de ces propriétés est vraie, disons la \(n\)-ème, alors la \((n+1)\)-ème est automatiquement vraie aussi.
Exemple: Supposons que l'on ait devant nous une très longue table sur laquelle sont posés une infinité d'ordinateurs, numérotés \(1,2,3,\dots\). On découvre avec effroi que sur chacun de ces ordinateurs est installé un système opérationnel propriétaire, issu d'une grande compagnie.
La méthode de démonstration par récurrence consiste à donner
une démonstration dans laquelle on utilise
une structure semblable à celle de
ce dernier exemple. On la résume comme suit:
Montrer par récurrence
qu'une infinité de propriétés \(\mathcal{P}(n)\) (\(n=1,2,3,\dots\)) sont vraies,
cela consiste
Si on peut effectivement vérifier ces deux étapes, alors 1. implique que \(\mathcal{P}(1)\) est vraie, mais alors 2. implique que \(\mathcal{P}(2)\) est vraie aussi, mais alors 2. implique que \(\mathcal{P}(3)\) est vraie aussi, etc. Ainsi, on a bien vérifié que \(\mathcal{P}(n)\) est vraie pour tout \(n\geqslant 1\).
\(\bigstar\) Pour que le pas d'induction ait une chance de fonctionner, il faut évidemment que les propriétés \(\mathcal{P}(n)\) et \(\mathcal{P}(n+1)\) puissent être mises en relation! Et là, la difficulté est de travailler avec un \(n\) quelconque, dont on ne spécifie pas la valeur; dans les situations concrètes, ceci implique en général un calcul littéral, dans lequel on manipule ce \(n\) inconnu.
Exemple:
Nous allons montrer que
pour tout \(n\in \mathbb{N}^*\),
\[
\boxed{1+2+3+4+\cdots +n=\frac{n(n+1)}{2}\,.}
\]
Commençons par nommer les deux membres de l'identité ci-dessus, en posant
\[
a_n:=
1+2+3+4+\cdots +n\,,\qquad\text{ et }\qquad
b_n:=\frac{n(n+1)}{2}\,.
\]
Notre but est donc de vérifier que \(a_n=b_n\) pour tout \(n\geqslant 1\).
Pour un \(n\) spécifique pas trop grand, on peut toujours le vérifier
en calculant la valeur de \(a_n\), puis celle de \(b_n\), puis de voir si elles
sont égales. Par exemple,
Exemple: En utilisant la même technique, on peut montrer que pour tout \(n\in \mathbb{N}\), \[ 1^2+2^2+3^2+4^2+\cdots +n^2=\frac{n(n+1)(2n+1)}{6}\,. \] (Pour une preuve alternative, plus géométrique, voir ici (Mathologer).) On utilisera cette formule dans le chapitre sur l'intégration.
Rappelons la définition des coefficients binômiaux. Pour un entier \(n\geqslant 1\) quelconque, et pour tout \(1\leqslant k\leqslant n\), \[ \binom{n}{k}:= \frac{n!}{k!(n-k)!} \] En combinatoire, \(\binom{n}{k}\) compte le nombre de façons d'arranger \(k\) objets indistingables dans \(n\) boîtes (un objet par boîte).
Lemme:(formule du binôme de Newton) Soient \(x,y\in \mathbb{R}\). Alors pour tout entier \(n\geqslant 1\), \[ (x+y)^n=\sum_{k=0}^n\binom{n}{k}x^{n-k}y^k\,. \]
(Voir la vidéo)
Plusieurs choses présentées ici sur la méthode de preuve par induction se retrouvent dans les textes classiques. Voir aussi la vidéo de Michael Penn.