Définition Soit $P(n)$ une propriété dépendant d'un entier $n \geqslant n_0$. Pour montrer que $P(n)$ est vraie pour tout $n \geqslant n_0$, le raisonnement par récurrence se fait en 3 étapes. Initialisation Vérifier que $\textcolor{#1d4ed8}{P(n_0)}$ est vraie (le plus souvent $n_0 = 0$ ou $1$). Hérédité Soit $n \geqslant n_0$ quelconque. Supposer $P(n)$ vraie (hypothèse de récurrence) et démontrer $\textcolor{#b91c1c}{P(n+1)}$. Conclusion D'après le principe de récurrence, $P(n)$ est vraie pour tout entier $n \geqslant n_0$.À retenir
Démontrer par récurrence que pour tout entier $n \geqslant 0$ : $2^n \geqslant n+1$. Posons $P(n) : 2^n \geqslant n+1$. Initialisation ($n=0$) : $2^0 = 1$ et $0+1 = 1$. Donc $\textcolor{#1d4ed8}{P(0)}$ est vraie. Hérédité : soit $n \geqslant 0$ tel que $2^n \geqslant n+1$. Alors : Donc $2^{n+1} \geqslant (n+1)+1$ : $\textcolor{#b91c1c}{P(n+1)}$ est vraie. Conclusion : par récurrence, $P(n)$ est vraie pour tout $n \geqslant 0$.Exemple type
$$2^{n+1} = 2 \times 2^n \geqslant 2(n+1) = 2n+2 \geqslant n+2$$
Pièges classiques