Exemples détaillés
Exemple 1 – Divisibilité de \(4^n + 2\)
Montrer que pour tout entier naturel \(n\), le nombre \(4^n + 2\) est divisible par \(3\).
Pour tout entier naturel \(n\), on considère la propriété
\[
P_n : « 4^n + 2 \text{ est divisible par } 3 ».
\]
1) Initialisation
On commence par le plus petit entier considéré : ici \(n = 0\).
\[
4^0 + 2 = 1 + 2 = 3.
\]
Or \(3\) est divisible par \(3\). Donc \(P_0\) est vraie.
2) Hérédité
On suppose maintenant qu'il existe un entier naturel \(n\) tel que
\(P_n\) soit vraie. C'est notre hypothèse de récurrence :
\[
4^n + 2 \text{ est divisible par } 3.
\]
On veut montrer que \(P_{n+1}\) est vraie, c'est-à-dire que \(4^{\,n+1} + 2\)
est divisible par \(3\).
On part de l'expression à étudier :
\[
4^{\,n+1} + 2 = 4 \times 4^n + 2.
\]
On cherche à faire apparaître \(\,\color{#d32f2f}{4^n + 2}\,\),
qui figure dans l'hypothèse de récurrence :
\[
4^{\,n+1} + 2
= 4 \times 4^n + 2\]
\[
4^{\,n+1} + 2 = (3+1)\times 4^n + 2\]
\[
4^{\,n+1} + 2 = 3 \times 4^n + 1 \times 4^n +2\]
\[
4^{\,n+1} + 2 = 3 \times 4^n + \color{#d32f2f}{\bigl(4^n + 2\bigr)}.
\]
D'après l'hypothèse de récurrence, la quantité
\(\color{#d32f2f}{4^n + 2}\) est divisible par \(3\).
Le terme \(3 \times 4^n\) est aussi divisible par \(3\).
La somme de deux nombres divisibles par \(3\) est encore divisible par \(3\).
Donc \(4^{\,n+1} + 2\) est divisible par \(3\) :
la propriété \(P_{n+1}\) est vraie.
3) Conclusion
On a montré :
- \(P_0\) est vraie (initialisation).
- Pour tout entier naturel \(n\), \(P_n \Rightarrow P_{n+1}\) (hérédité).
Le principe de récurrence permet donc d'affirmer que, pour tout entier naturel \(n\),
le nombre \(4^n + 2\) est divisible par \(3\).
Exemple 2 – Somme des carrés
Montrer que pour tout entier naturel non nul \(n\),
\[
1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}.
\]
Pour tout entier naturel non nul \(n\), on pose
\[
P_n : « 1^2 + 2^2 + \dots + n^2
= \frac{n(n+1)(2n+1)}{6} ».
\]
1) Initialisation
Pour \(n = 1\) :
\[
1^2 = 1
\quad\text{et}\quad
\frac{1 \times (1+1) \times (2 \times 1 + 1)}{6}
= \frac{1 \times 2 \times 3}{6} = 1.
\]
Les deux expressions sont égales, donc \(P_1\) est vraie.
2) Hérédité
On suppose qu'il existe un entier naturel non nul \(n\) tel que \(P_n\) soit vraie :
\[
1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}.
\]
On veut montrer que cela entraîne \(P_{n+1}\), c'est‑à‑dire :
\[
1^2 + 2^2 + \dots + n^2 + (n+1)^2
= \frac{(n+1)(n+2)(2n+3)}{6}.
\]
On part de la somme donnée par l'hypothèse de récurrence :
\[
{\color{#d32f2f}{1^2 + \dots + n^2}}\color{black}
= {\color{#d32f2f}{\dfrac{n(n+1)(2n+1)}{6}}}\color{black}.
\]
On ajoute jusqu'à \( (n+1)^2\) dans chaque membre :
\[
{\color{#d32f2f}{1^2 + \dots + n^2}}\color{black} + (n+1)^2
= {\color{#d32f2f}{\dfrac{n(n+1)(2n+1)}{6}}}\color{black} + (n+1)^2.
\]
On factorise dans le membre de droite par \((n+1)\) :
\[
{\color{#d32f2f}{1^2 + \dots + n^2}}\color{black} + (n+1)^2 = (n+1)\left[\frac{n(2n+1)}{6} + (n+1)\right].
\]
On met tout au même dénominateur \(6\) :
\[
\frac{n(2n+1)}{6} + (n+1)
= \frac{n(2n+1) + 6(n+1)}{6}
= \frac{2n^2 + n + 6n + 6}{6}
= \frac{2n^2 + 7n + 6}{6}.
\]
D'où
\[
1^2 + \dots + (n+1)^2
= (n+1) \times \frac{2n^2 + 7n + 6}{6}.
\]
On factorise enfin le polynôme \(2n^2 + 7n + 6\) :
\[
2n^2 + 7n + 6 = (2n+3)(n+2).
\]
On obtient alors
\[
1^2 + \dots + (n+1)^2
= \frac{(n+1)(n+2)(2n+3)}{6},
\]
ce qui est exactement l'égalité souhaitée pour \(n+1\).
La propriété \(P_{n+1}\) est donc vraie.
3) Conclusion
On a montré que \(P_1\) est vraie, et que pour tout entier naturel non nul
\(n\), \(P_n \Rightarrow P_{n+1}\). D'après le principe de récurrence,
la formule est vraie pour tout entier naturel non nul \(n\).
Exemple 3 – Inégalité \(2^n \geq n + 1\)
Montrer que pour tout entier naturel \(n\), on a \(2^n \geq n + 1\).
Pour tout entier naturel \(n\), on pose
\[
P_n : « 2^n \geq n + 1 ».
\]
1) Initialisation
Pour \(n = 0\) :
\[
2^0 = 1 \quad\text{et}\quad 0 + 1 = 1.
\]
On a bien \(2^0 \geq 0 + 1\). Donc \(P_0\) est vraie.
2) Hérédité
On suppose qu'il existe un entier naturel \(n\) pour lequel
\(P_n\) est vraie :
\[
2^n \geq n + 1.
\]
On veut montrer que cela implique
\[
2^{\,n+1} \geq n + 2.
\]
On écrit
\[
2^{\,n+1} = 2 \times 2^n.
\]
En utilisant l'hypothèse \(\color{#d32f2f}{2^n \geq n + 1}\), et en multipliant chaque membre par 2 on obtient
\[
\color{black}2 \times \color{#d32f2f}{2^n \geq} \color{black}2 \times \color{#d32f2f}{(n + 1)} .
\]
Et donc :
\[
2^{\,n+1}\geq 2n + 2 \]
De plus, pour tout entier \(n \geq 0\),
\[
2n + 2 \geq n + 2
\]
car \(2n + 2 - (n + 2) = n \geq 0\).
Ainsi
\[
2^{\,n+1} \geq n + 2
\]
et \(P_{n+1}\) est vraie.
3) Conclusion
On a \(P_0\) vraie et, pour tout entier naturel \(n\),
\(P_n \Rightarrow P_{n+1}\). Par récurrence, pour tout entier naturel
\(n\), on a bien \(2^n \geq n + 1\).
Exemple 4 – Suite définie par récurrence
On considère la suite \((u_n)\) définie par
\[
u_0 = 1
\quad\text{et}\quad
u_{n+1} = 2u_n + 1 \quad\text{pour tout entier } n \geq 0.
\]
On veut démontrer, par récurrence, que pour tout entier \(n\),
\[
u_n = 2^{\,n+1} - 1.
\]
Pour tout entier \(n\), on pose
\[
P_n : « u_n = 2^{\,n+1} - 1 ».
\]
1) Initialisation
Pour \(n = 0\), on calcule \(u_0\) à partir de la définition :
\[
u_0 = 1.
\]
De l'autre côté, la formule à démontrer donne
\[
2^{\,0+1} - 1 = 2^1 - 1 = 2 - 1 = 1.
\]
On obtient bien la même valeur. Donc \(P_0\) est vraie.
2) Hérédité
On suppose qu'il existe un entier naturel \(n\) tel que
\(P_n\) soit vraie, c'est‑à‑dire :
\[
u_n = 2^{\,n+1} - 1.
\]
On veut montrer que cela implique \(P_{n+1}\), c'est‑à‑dire
\[
u_{n+1} = 2^{\,n+2} - 1.
\]
On part de la relation de récurrence :
\[
u_{n+1} = 2u_n + 1.
\]
On remplace \(u_n\) par l'expression de l'hypothèse de récurrence
\(\,\color{#d32f2f}{u_n = 2^{\,n+1} - 1}\,\) :
\[
u_{n+1}
= 2 \times \color{#d32f2f}{\bigl(2^{\,n+1} - 1\bigr)} \color{black}+ 1
= 2 \times 2^{\,n+1} - 2 + 1.
\]
Or \(2 \times 2^{\,n+1} = 2^{\,n+2}\). Donc
\[
u_{n+1} = 2^{\,n+2} - 1,
\]
ce qui est exactement la formule annoncée pour le rang \(n+1\).
La propriété \(P_{n+1}\) est donc vraie.
3) Conclusion
On a vérifié que \(P_0\) est vraie puis que, pour tout entier naturel \(n\),
\(P_n \Rightarrow P_{n+1}\). D'après le principe de récurrence,
pour tout entier naturel \(n\),
\[
u_n = 2^{\,n+1} - 1.
\]