RAISONNEMENT PAR RECURRENCE
Cours
|
I) Présentation du raisonnement par récurrence
Nous allons commencer par un exemple pour illustrer l'utilité du raisonnement par récurrence.
Considérons la suite de nombres \(\left(u_{n}\right)_{n\in \mathbb{N}}\) définie par \(u_{0}=1\) et \(u_{n}=u_{n-1}+2\).
Dans le tableau ci-dessous, nous avons indiqué en première ligne les valeurs prises par \(n\) et dans la seconde ligne, les termes de la suite correspondant à ces valeurs de \(n\).
| \(n\) |
\(0\) |
\(1\) |
\(2\) |
\(3\) |
\(4\) |
| \(\displaystyle u_{n}\) |
\(1\) |
\(3\) |
\(5\) |
\(7\) |
\(9\) |
Pour rappel, nous calculons \(u_{1}\) de la façon suivante :
\[
\begin{align*}
u_{1}&=u_{1-1}+2\\
&=u_{0}+2\\
&=1+2\\
&=3,
\end{align*}
\]
\(u_{2}\) de la façon suivante :
\[
\begin{align*}
u_{2}&=u_{2-1}+2\\
&=u_{1}+2\\
&=3+2\\
&=5,
\end{align*}
\]
ainsi de suite...
Il semblerait que chaque terme de la suite \(u_{n}\) soit égal à \(2n+1\). En effet, nous pouvons compléter le tableau précédent en ajoutant une ligne où figure le calcul de \(2n+1\) pour les valeurs de \(n\) que nous considérons, et nous constatons que les valeurs sont identiques à celles de la ligne du dessus :
| \(n\) |
\(0\) |
\(1\) |
\(2\) |
\(3\) |
\(4\) |
| \(\displaystyle u_{n}\) |
\(1\) |
\(3\) |
\(5\) |
\(7\) |
\(9\) |
| \(2n+1\) |
\(1\) |
\(3\) |
\(5\) |
\(7\) |
\(9\) |
Pour l'instant,
nous n'avons rien prouvé. A ce stade, nous pouvons seulement conjecturer que :
Pour tout \(n\in \mathbb{N}\), \(u_{n}=2n+1\).
Il s'agit maintenant de démontrer ce résultat, s'il est vrai. En effet, pour le moment, nous savons que c'est le cas seulement lorsque \(n=0,1,2,3,4\).
Par exemple, pour l'instant, je ne sais pas si la relation est vérifiée pour \(n=10\).
Mais cependant, je peux dire que si elle est vérifiée pour \(n=10\), alors elle l'est aussi pour \(n=11\). En effet supposons que la relation soit vraie pour \(n=10\), c'est-à-dire que nous avons \(u_{10}=2\times 10+1=21\). Alors :
\[
\begin{align*}
u_{11}&=u_{10}+2\\
&=21+2\\
&=23\\
&=2\times 11+1,
\end{align*}
\]
et la relation est vérifiée pour \(n=11\).
Nous aurions pu faire le même constat pour d'autres valeurs de \(n\).
De façon plus générale, si nous
supposons la relation vraie à l'ordre \(n\), c'est-à-dire :
\[
u_{n}=2n+1,
\]
alors nous pouvons
démontrer qu'elle est vraie à l'ordre \(n+1\). En effet :
\[
\begin{align*}
u_{n+1}&=u_{n}+2\\
&=2n+1+2\text{ (par hypothèse)}\\
&=2n+2+1\\
&=2(n+1)+1.
\end{align*}
\]
La relation est bien vraie à l'ordre \(n+1\).
De fait, si la formule est vérifiée pour \(n=0\), alors elle l'est automatiquement pour \(n=1\). et si elle est vraie pour \(n=1\), alors elle l'est aussi pour \(n=2\). Et si elle est vraie pour \(n=2\), alors elle l'est aussi pour \(n=3\). Ainsi de suite pour tous les entiers naturels.
Il reste donc à démontrer que cette formule est bien vérifiée pour \(n=0\).
Etant donné que :
\[
2\times 0+1=1=u_{0},
\]
nous pouvons conclure que c'est le cas.
La démonstration ci-dessus est en réalité une démonstration
par récurrence, même si celle-ci est encore un brouillon.
Dans ce qui suit, nous allons davantage formaliser ce type de démonstration.
II) Enoncé du raisonnement par récurrence
Théorème 1
On souhaite démontrer qu'une propriété \(\mathcal{P}(n)\) est vraie pour tout entier naturel \(n\) supérieur ou égal à un certain entier naturel \(n_{0}\).
Si \(\mathcal{P}(n_{0})\) est vraie, et que pour tout entier naturel \(n\geq n_{0}\), \(\mathcal{P}(n)\) implique \(\mathcal{P}(n+1)\) vraie, alors la propriété \(\mathcal{P}(n)\) est vraie pour tout \(n\geq n_{0}\).
Une démonstration par récurrence s'effectue en plusieurs étapes.
1) Indiquer la propriété que l'on souhaite démontrer
en n'oubliant pas de préciser les valeurs de \(n\) pour lesquelles on va la démontrer.
2) L'initialisation : On vérifie que la propriété est vraie pour la première valeur de \(n\) envisagée, c'est-à-dire pour \(n=n_{0}\).
3) L'hérédité : soit un entier naturel \(n\) tel que \(n\geq n_{0}\). On suppose que la propriété est vraie au rang \(n\) et on démontre sous cette hypothèse que la propriété est aussi vraie au rang \(n+1\).
4) La conclusion : on énonce la propriété à présent démontrée.
Rédigeons à présent proprement la démonstration par récurrence de ce que nous avons esquissé dans la partie I de ce cours.
Soit \(\mathcal{P}(n)\) la propriété : "\(u_{n}=2n+1\)".
Initialisation : Vérifions que \(\mathcal{P}(0)\) est vraie.
Nous avons :
\[
2\times 0+1=1=u_{0},
\]
donc \(\mathcal{P}(0)\) est vraie.
Hérédité : Soit un entier \(n \geq 0\). Supposons que la propriété \(\mathcal{P}(n)\) est vraie :
\[
u_{n}=2n+1.
\]
Montrons alors que la propriété \(\mathcal{P}(n+1)\) est vraie.
\[
\begin{align*}
u_{n+1}&=u_{n}+2\\
&=2n+1+2\text{ (par hypothèse de récurrence)}\\
&=2n+2+1\\
&=2(n+1)+1,
\end{align*}
\]
donc la propriété \(\mathcal{P}(n+1)\) est aussi vraie.
Conclusion :
\[
\boxed{u_{n}=2n+1, \quad \forall n\in \mathbb{N}}.
\]
Nous effectuerons dans les feuilles d'exercices de nombreuses démonstrations par récurrence.