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.

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.

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. 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,

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)\):=''pour l'entier \(n\), on a \(a_n=b_n\)''
Montrons, par récurrence, que pour tout \(n\geqslant 1\), la propriété \(\mathcal{P}(n)\) est vraie.
  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 comme \[ b_{n+1}=\frac{(n+1)((n+1)+1)}{2}=\frac{(n+1)(n+2)}{2}\,, \] 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. Mais comme l'initialisation a été vérifiée, on a donc bien montré que \(\mathcal{P}(n)\) est vraie pour tout \(n\geqslant 1\).

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.



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)

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.





---- (Dernière modification: 2022-10-31 (07:27:49)) ----