Raisonnement par récurrence
Lorsque l’on souhaite démontrer une proposition mathématique qui dépend d’un entier \(n\), il est parfois possible de démontrer cette proposition par récurrence.
Pour tout entier \(n\), on note \(\mathcal{P}(n)\) la proposition qui nous intéresse. La démonstration par récurrence comporte trois étapes
- Initialisation : On montre qu’il existe un entier \(n_0\) pour lequel \(\mathcal{P}(n_0)\) est vraie ;
- Hérédité : on montre que, si pour un certain entier \(n\geqslant n_0\), \(\mathcal{P}(n)\) est vraie, alors \(\mathcal{P}(n+1)\) l’est également ;
- Conclusion : on en conclut que pour entier \(n\geqslant n_0\), la proposition \(\mathcal{P}(n)\) est vraie.
Le principe du raisonnement par récurrence rappelle les dominos que l’on aligne et que l’on fait tomber, les uns à la suite des autres.
On positionne les dominos de telle sorte que, dès que l’un tombe, peu importe lequel, il entraîne le suivant dans sa chute. C’est l’hérédité. Seulement, encore faut-il faire effectivement tomber le premier domino, sans quoi rien ne se passe : c’est l’initialisation.
Si ces deux conditions sont remplies, on est certain qu’à la fin, tous les dominos seront tombés : c’est notre Conclusion.
Exemple (tiré de l’épreuve de spécialité de Polynésie 2022) : On considère la suite \((u_n)\) définie par \(u_0=1\) et, pour tout entier naturel \(n\), \[u_{n+1}=\dfrac{u_n}{1+u_n}\]
A l’aide de cette expression, il est possible de calculer les termes de la suite de proche en proche.
- \(u_1 = \dfrac{u_0}{1+u_0}=\dfrac{1}{1+1}=\dfrac{1}{2}\).
- \(u_2= \dfrac{u_1}{1+u_1}=\dfrac{ \frac{1}{2}}{1+\frac{1}{2}}=\dfrac{ \frac{1}{2}}{\frac{3}{2}}=\dfrac{1}{3} \).
- \(u_3= \dfrac{u_2}{1+u_2}=\dfrac{ \frac{1}{3}}{1+\frac{1}{3}}=\dfrac{ \frac{1}{3}}{\frac{4}{3}}=\dfrac{1}{4} \).
- \(\ldots\)
Toutefois, il n’est pas possible de calculer \(u_{50}\) sans calculer tous les termes précédents… On souhaiterait déterminer une expression de \(u_n\) en fonction de \(n\) pour tout entier naturel \(n\).
D’après les premiers termes de notre suite, il semblerait que pour tout entier naturel \(n\), on ait \(u_{\color{red}{n}}=\dfrac{1}{\color{red}n\color{black}+1}\). Cette formule fonction pour les rangs 0, 1, 2 et 3mais qu’en est-il pour le reste ? Nous allons montrer qu’elle fonctionne pour tous les rangs en procédant par récurrence.
Pour \(n\in\mathbb{N}\), on note \(\mathcal{P}(\color{red}n\color{black})\) la proposition « \(u_{\color{red}n}=\dfrac{1}{\color{red}n\color{black}+1}\) ».
- Initialisation : Pour \(n=\color{red}0\). \[\dfrac{1}{\color{red}0\color{black}+1}=\dfrac{1}{1}=1=u_0\] La propriété est vraie au rang 0.
- Hérédité : Soit \(n\in\mathbb{N}\). Supposons que \(\mathcal{P}(\color{red}n\color{black})\) est vraie. On a donc \(u_{\color{red}n} = \dfrac{1}{\color{red}n\color{black}+1}\).A partir de ce résultat, on souhaite démontrer que \(\mathcal{P}(\color{blue}{n+1})\) est vraie, c’est-à-dire que \(u_{\color{blue}{n+1}}=\dfrac{1}{\color{blue}{n+1}+1}=\dfrac{1}{n+2}\)
Nous avons donc \( u_n = \dfrac{1}{n+1}\). Or, \(u_{n+1} = \dfrac{u_n}{1+u_n}\). Ainsi,
\[ u_{n+1} = \dfrac{\frac{1}{n+1}}{\frac{1}{n+1}+1}=\dfrac{\frac{1}{n+1}}{\frac{n+2}{n+1}}=\dfrac{1}{n+2} \]
On trouve bien que \(u_{\color{blue}{n+1}}=\dfrac{1}{\color{blue}{n+1}+1}\) : \( \mathcal{P}( \color{blue}{n+1})\) est donc vraie.
- Conclusion : La propriété est vraie au rang 0 et est héréditaire, elle est donc vraie pour tout entier \(n\).
Nous avons montré que pour tout entier naturel \(n\), on a bien \(u_n= \dfrac{1}{n+1}\).
Inégalité de Bernoulli : Soit \(a\) un réel strictement positif. Pour tout entier naturel \(n\), \[(1+a)^n \geqslant 1+na\]
Nous allons démontrer cette propriété par récurrence. Fixons \(a\) un réel strictement positif.
Pour tout entier naturel \(n\), on note \(\mathcal{P}(n)\) la proposition « \((1+a)^n \geqslant 1+na\) ».
- Initialisation : Prenons \(n=0\). \((1+a)^0 = 1\) et \(1+ 0 \times a = 1\). On a bien \((1+a)^0 \geqslant 1+0 \times a\). \(\mathcal{P}(0)\) est donc vraie.
- Hérédité : Soit \(n\in\mathbb{N}\). Supposons que \(\mathcal{P}(n)\) est vraie. On a donc \((1+a)^n \geqslant 1+na\).En multipliant des deux côtés de l’inégalité par \((1+a)\), qui est strictement positif, on obtient \[(1+a)^{n+1}\geqslant (1+na)(1+a)\] Or,
\[(1+na)(1+a)=1+na+a+na^2=1+(n+1)a+na^2 \geqslant 1+(n+1)a\] Ainsi, \[(1+a)^{n+1} \geqslant 1+(n+1)a\] \(\mathcal{P}(n+1)\) est donc vraie. - Conclusion : \(\mathcal{P}(0)\) est vraie et, si \(\mathcal{P}(n)\) est vraie, \(\mathcal{P}(n+1)\) est vraie. Ainsi, d’après le principe de récurrence, \(\mathcal{P}(n)\) est vraie pour tout entier naturel \(n\).
Ainsi, pour tout réel strictement positif \(a\) et pour tout entier naturel \(n\), \((1+a)^n \geqslant 1+na\)
Cette inégalité peut donc être montrée à l’aide d’un argument de convexité.
Suite majorée, minorée, bornée
Soit \((u_n)\) une suite réelle. On dit que…
- …\((u_n)\) est majorée s’il existe un réel \(M\) tel que, pour tout entier naturel \(n\), \(u_n \leqslant M\).
- …\((u_n)\) est minorée s’il existe un réel \(m\) tel que, pour tout entier naturel \(n\), \(u_n \geqslant m\).
- …\((u_n)\) est bornée si \((u_n)\) est à la fois majorée et minorée.
Exemple : Pour tout \(n\), on pose \(u_n=\cos (n)\). La suite \((u_n)\) est bornée puisque, pour tout entier \(n\), \(-1 \leqslant u_n \leqslant 1\).
Exemple : Pour tout entier naturel \(n\), on pose \(v_n=n^2+1\). La suite \((v_n)\) est minorée puisque pour tout \(n\), \(v_n\geqslant 1\). En revanche, elle n’est pas majorée.
Exemple : Pour tout entier naturel \(n\), on pose \(w_n=(-1)^n \, n\). La suite \((w_n)\) n’est ni majorée, ni minorée.
Exemple : On considère la suite \((u_n)\) définie par \(u_0 = 5\) et pour tout entier naturel \(n\), \(u_{n+1}=0.5u_n + 2\).
Pour tout entier naturel \(n\), on note \(\mathcal{P}(n)\) la proposition « \(u_n \geqslant 4\) ».
- Initialisation : On a bien \(u_0 \geqslant 4\). \(\mathcal{P}(0)\) est donc vraie.
- Hérédité : Soit \(n\in\mathbb{N}\). Supposons que \(\mathcal{P}(n)\) est vraie, c’est-à-dire \(u_n \geqslant 4\). Ainsi, \[0.5 u_n \geqslant 2\] et \[0.5u_n+2 \geqslant 4\] c’est-à-dire \[u_{n+1}\geqslant 4\] \(\mathcal{P}(n+1)\) est vraie.
- Ainsi, \(\mathcal{P}(0)\) est vraie et la proposition \(\mathcal{P}\) est héréditaire. D’après le principe de récurrence, on en conclut que pour tout entier naturel \(n\), \(\mathcal{P}(n)\) est vraie.
Suites croissantes, suites décroissantes
Soit \((u_n)\) une suite réelle.
- On dit que \((u_n)\) est croissante à partir de \(n_0\) si, pour tout entier naturel \(n\geqslant n_0\), \(u_{n+1} \geqslant u_n\).
- On dit que \((u_n)\) est décroissante à partir de \(n_0\) si, pour tout entier naturel \(n\geqslant n_0\), \(u_{n+1} \geqslant u_n\).
Exemple : On considère la suite \((u_n)\) définie par \(u_0=4\) et telle que, pour tout entier naturel \(n\), \(u_{n+1}=\sqrt{5+u_n}\).
Pour tout entier naturel \(n\), on note \(\mathcal{P}(n)\) la proposition \(0\leqslant u_{n+1} \leqslant u_n\). Montrons que \(\mathcal{P}(n)\) est vraie pour tout \(n\). On démontrera ainsi que la suite \((u_n)\) est décroissante et minorée par 0, un résultat qui nous intéressera fortement dans un prochain chapitre…
- Initialisation : \(u_0=4\), \(u_1=\sqrt{5+4}=\sqrt{9}=3\). On a bien \(0 \leqslant u_1 \leqslant u_0\). \(\mathcal{P}(0)\) est vraie.
- Hérédité : Soit \(n\in\mathbb{N}\). Supposons que \(\mathcal{P}(n)\) est vraie. On a alors
\[0\leqslant u_{n+1} \leqslant u_n\]
En ajoutant 5 à chaque membre, on obtient
\[5\leqslant u_{n+1} +5\leqslant u_n+5\]
On souhaite « appliquer la racine carrée » à cette inégalité. La fonction \(x\mapsto \sqrt{x}\) étant croissante, l’appliquer ne changera pas le sens de l’inégalité. On a donc bien
\[ \sqrt{5} \leqslant \sqrt{u_{n+1}+5} \leqslant \sqrt{u_n+5}\]
D’une part, \(\sqrt{5}>0\). D’autre part, \(\sqrt{u_{n+1}+5}=u_{n+2}\) et \(\sqrt{u_{n}+5}=u_{n+1}\). Ainsi
\[0 \leqslant u_{n+2} \leqslant u_{n+1}\]
La proposition \(\mathcal{P}(n+1)\) est donc vraie. - Conclusion : \(\mathcal{P}(0)\) est vraie et \(\mathcal{P}\) est héréditaire. Par récurrence, \(\mathcal{P}(n)\) est vraie pour tout entier naturel \(n\).