Raisonnement par récurrence
1. Le principe
On veut démontrer qu'une propriété dépendant d'un entier $n$ est vraie pour tous les entiers à partir d'un certain rang. On ne peut pas tout vérifier un par un : on utilise un effet « domino ».
Soit $\mathcal{P}(n)$ une propriété définie pour tout entier $n \geqslant n_0$. Si :
- Initialisation : $\mathcal{P}(n_0)$ est vraie ;
- Hérédité : pour tout $n \geqslant n_0$, si $\mathcal{P}(n)$ est vraie alors $\mathcal{P}(n+1)$ est vraie ;
alors $\mathcal{P}(n)$ est vraie pour tout entier $n \geqslant n_0$.
2. Un exemple rédigé
Exemple. Soit $(u_n)$ la suite définie par $u_0 = 1$ et, pour tout $n \in \mathbb{N}$, $u_{n+1} = 2u_n + 1$. Montrons que pour tout $n \in \mathbb{N}$, $u_n = 2^{n+1} - 1$.
Initialisation : $2^{0+1} - 1 = 1 = u_0$. La propriété est vraie au rang $0$.
Hérédité : supposons que $u_n = 2^{n+1} - 1$ pour un entier $n$ fixé. Alors :
$$u_{n+1} = 2\left(2^{n+1} - 1\right) + 1 = 2^{n+2} - 2 + 1 = 2^{n+2} - 1.$$La propriété est donc vraie au rang $n+1$.
Conclusion : par récurrence, pour tout $n \in \mathbb{N}$, $u_n = 2^{n+1} - 1$.
3. La vidéo
4. Exercices
Démontrer que pour tout entier $n \geqslant 1$ :
$$1 + 2 + \cdots + n = \frac{n(n+1)}{2}.$$Voir la correctionMasquer la correction
Initialisation : pour $n = 1$, le membre de gauche vaut $1$ et $\dfrac{1 \times 2}{2} = 1$. La propriété est vraie.
Hérédité : supposons $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$ pour un entier $n \geqslant 1$. Alors :
$$1 + \cdots + n + (n+1) = \frac{n(n+1)}{2} + (n+1) = \frac{(n+1)(n+2)}{2}.$$Conclusion : la formule est vraie pour tout entier $n \geqslant 1$.
Démontrer que pour tout entier $n \in \mathbb{N}$, $4^n - 1$ est divisible par $3$.
Voir la correctionMasquer la correction
Initialisation : $4^0 - 1 = 0$, qui est divisible par $3$.
Hérédité : supposons $4^n - 1 = 3k$ avec $k \in \mathbb{Z}$. Alors :
$$4^{n+1} - 1 = 4 \times 4^n - 1 = 4(3k + 1) - 1 = 12k + 3 = 3(4k + 1).$$Donc $4^{n+1} - 1$ est divisible par $3$.
Conclusion : pour tout $n \in \mathbb{N}$, $4^n - 1$ est divisible par $3$.