II.7 Preuves par récurrence

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.

En mathématiques, on a souvent besoin de montrer qu'une infinité de propriétés sont vraies simultanément: \(\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 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''.

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 d'obtenir la réponse: parcourir tout l'univers jusqu'à trouver une galaxie contenant exactement \(n\) planètes sur lesquelles on trouve la vie.

Si on a de la chance, on peut espérer étudier la véracité de ces propriétés \(\mathcal{P}(n)\) en profitant de certaines relations pouvant exister entre elles, pour des \(n\) différents.

Dans le cas de la récurrence, on s'intéresse à une relation entre les paires d'entiers consécutifs, \(n\) et \(n+1\), et la relation considérée est la suivante: si \(\mathcal{P}(n)\) est vraie, alors \(\mathcal{P}(n+1)\) est vraie aussi.

Exemple: Dans l'exemple du dessus (galaxies), il n'y a aucune corrélation du genre entre les propriétés \(\mathcal{P}(n)\) pour des \(n\) différents, puisque savoir que \(\mathcal{P}(n)\) est vraie n'implique pas forcément que \(\mathcal{P}(n+1)\) soit 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.

On suppose que ces ordinateurs sont tous allumés, et que pour tout \(n\), le \(n\)-ème ordinateur envoie constamment des données non-cryptées vers son voisin \(n+1\). Dans ce cas, il est absolument certain que si l'ordinateur \(n\) est infecté par un virus, alors l'ordinateur \(n+1\) est infecté aussi. En d'autres termes, si on définit la propriété \(\mathcal{P}(n)=\)''le \(n\)ème ordinateur est infecté par un virus'', on sait que si \(\mathcal{P}(n)\) est vraie, alors \(\mathcal{P}(n+1)\) est vraie aussi.

Ceci a la conséquence suivante: si un seul de ces ordinateurs est infecté, alors tous les suivants le sont aussi. En particulier, si le premier est infecté, alors tous sont infectés.

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

  1. à vérifier que la première propriété \(\mathcal{P}(1)\) est vraie, (c'est l'initialisation), puis
  2. à vérifier que quel que soit l'indice \(n\geqslant 1\), si \(\mathcal{P}(n)\) est vraie, alors cela entraîne que \(\mathcal{P}(n+1)\) est vraie aussi (c'est le pas d'induction).

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. Par ce procédé, on démontre donc bien que \(\mathcal{P}(n)\) est vraie pour tout \(n\geqslant 1\).

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, quel que soit \(n\)! 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}\,. \] 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,

On voit donc que \(a_1=b_1\) et \(a_2=b_2\).

On pourrait continuer à vérifier la relation ''\(a_n=b_n\)'' pour des \(n\) toujours plus grands, en calculant séparément les nombres \(a_n\) et \(b_n\) ''à la main'', et en vérifiant qu'ils sont effectivement égaux. Mais ceci n'exclut pas qu'il existe un \(n\), éventuellement très grand, pour lequel \(a_n\neq b_n\)!

Définissons donc, pour tout \(n\geqslant 1\), la propriété \(\mathcal{P}(n)\) comme étant: ''pour l'entier \(n\), on a \(a_n=b_n\)''. Montrons, par récurrence, que \(\mathcal{P}(n)\) est vraie pour tout \(n\geqslant 1\).
  1. Initialisation: on a déjà vérifié plus haut, ''à la main'', que \(a_1=b_1\), et donc on sait que \(\mathcal{P}(1)\) est vraie.
  2. Pas d'induction: supposons que pour un \(n\) donné (dont on n'a pas besoin de spécifier la valeur), \(\mathcal{P}(n)\) est vraie , c'est-à-dire que l'on a effectivement \[ a_n=b_n\,. \] Pour montrer que ceci entraîne que \(\mathcal{P}(n+1)\) est vraie, on va faire un calcul, à l'issue duquel on obtiendra que \(a_{n+1}=b_{n+1}\). Or la structure du problème fait que \(a_{n+1}\) peut être relié à \(a_n\). En effet, \[ a_{n+1}=1+2+3+4+\cdots+ n+(n+1)=a_n+(n+1)\,. \] Mais, puisque l'on est en train de supposer que \(a_n=b_n\), on peut l'utiliser et faire un peu d'arithmétique: \[\begin{aligned} a_{n+1} &=b_n+(n+1)\\ &=\frac{n(n+1)}{2}+(n+1)\\ &=\frac{n(n+1)+2(n+1)}{2} =\frac{(n+1)(n+2)}{2}\,. \end{aligned}\] Mais puisque \[ \frac{(n+1)(n+2)}{2} =\frac{(n+1)((n+1)+1)}{2} =b_{n+1}\,, \] on a bien montré que \(a_{n+1}=b_{n+1}\). Ceci montre que si \(\mathcal{P}(n)\) est vraie, alors \(\mathcal{P}(n+1)\) est vraie aussi.
On a donc bien montré que \(\mathcal{P}(n)\) est vraie pour tout \(n\geqslant 1\).

Remarque: En utilisant la même technique, on peut montrer que pour tout \(n\in \mathbb{N}\), \[ \boxed{ 1^2+2^2+3^2+4^2+\cdots +n^2=\frac{n(n+1)(2n+1)}{6} } \] En fait il existe des formules semblables pour toute somme du type \[ 1^k+2^k+3^k+\cdots+n^k\,, \] où \(k\geqslant 1\) est un entier. Voir ici (Mathologer) pour plus d'informations.

Exemple: Posons, pour tout \(n\geqslant 1\), \(a_n=10^n-1\), et considérons l'affirmation \(\mathcal{P}(n)\) définie par ''\(a_n\) est un multiple de \(9\)''.

  1. Pour \(n=1\), on a \(a_1=10^1-1=9\), qui est un multiple de \(9\).
  2. Supposons que \(\mathcal{P}(n)\) est vraie, c'est-à-dire que \(a_n\) est un multiple de \(9\). Ceci s'exprime en disant qu'il existe un entier \(k\) tel que \(a_n=9k\). Remarquons alors qu'on peut écrire \[\begin{aligned} a_{n+1}=10^{n+1}-1 &=10\cdot 10^n-1\\ &=10(a_n+1)-1\\ &=10(9k+1)-1=9(\underbrace{10k+1}_{=:k'})\,. \end{aligned}\] Or puisque \(k\) est un entier, \(k'=10k+1\) est aussi un entier. Donc \(a_{n+1}=9k'\): \(a_{n+1}\) est aussi un multiple de \(9\), et donc \(\mathcal{P}(n+1)\) est vraie.
Ceci montre que \(\mathcal{P}(n)\) est vraie pour tout \(n\geqslant 1\).

La formule du binôme de Newton

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)

Voir aussi la vidéo de Michael Penn.

Dernière compilation: 2023-09-19 (18:16:34)

Sauf indication contraire, le contenu de ce document est soumis à une licence Creative Commons internationale, Attribution: Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 (CC BY-NC-SA 4.0)