Rédiger une démonstration par récurrence
Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.
Créer un compteMéthodes
Principe
Rédiger une démonstration par récurrence
Pour démontrer qu'une propriété $P(n)$ est vraie pour tout entier $n \geqslant n_{0}$, on rédige trois étapes :
- Initialisation : vérifier que $P(n_{0})$ est vraie (calcul direct).
- Hérédité : supposer $P(n)$ vraie pour un entier $n \geqslant n_{0}$ fixé (hypothèse de récurrence), puis démontrer que $P(n+1)$ est vraie. Il est conseillé d'écrire explicitement $P(n+1)$ en remplaçant $n$ par $n+1$.
- Conclusion : d'après le principe de récurrence, $P(n)$ est vraie pour tout $n \geqslant n_{0}$.
Attention
- Ne jamais oublier l'initialisation, même si elle paraît évidente.
- L'hypothèse de récurrence doit être clairement identifiée et effectivement utilisée dans la démonstration de l'hérédité.
- Bien distinguer « $P(n)$ vraie » (hypothèse) de « $P(n+1)$ vraie » (ce qu'on veut démontrer).
Exemple 1 : Démontrer une formule de somme
Exemple
Montrons par récurrence que pour tout entier $n \geqslant 1$ :
Initialisation ($n = 1$)
Le membre de gauche vaut $1$.
Le membre de droite vaut $\dfrac{1 \times 2}{2} = 1$.
Les deux membres sont égaux, donc $P(1)$ est vraie.
Hérédité
On suppose que $P(n)$ est vraie pour un certain entier $n \geqslant 1$, c'est-à-dire :
Montrons que $P(n+1)$ est vraie, c'est-à-dire que :
On part du membre de gauche de $P(n+1)$ :
$1 + 2 + \dots + (n+1) = \underbrace{(1 + 2 + \dots + n)}_{\text{H.R.}} + (n+1)$
$= \dfrac{n(n+1)}{2} + (n+1)$
$= \dfrac{n(n+1) + 2(n+1)}{2}$
$= \dfrac{(n+1)(n+2)}{2}$
On retrouve bien le membre de droite de $P(n+1)$, donc $P(n+1)$ est vraie.
Conclusion
D'après le principe de récurrence, pour tout entier $n \geqslant 1$ :
Exemple 2 : Démontrer un encadrement pour une suite récurrente
Exemple
Soit la suite $(u_{n})$ définie par $u_{0} = 2$ et $u_{n+1} = \dfrac{u_{n} + 4}{2}$ pour tout $n \in \mathbb{N}$.
Montrons par récurrence que pour tout $n \in \mathbb{N}$ : $2 \leqslant u_{n} \leqslant 4$.
Initialisation ($n = 0$)
$u_{0} = 2$, et on a bien $2 \leqslant 2 \leqslant 4$. Donc $P(0)$ est vraie.
Hérédité
On suppose que $2 \leqslant u_{n} \leqslant 4$ pour un certain $n \in \mathbb{N}$ (hypothèse de récurrence).
Montrons que $2 \leqslant u_{n+1} \leqslant 4$.
En partant de $2 \leqslant u_{n} \leqslant 4$, on ajoute $4$ à chaque membre :
$6 \leqslant u_{n} + 4 \leqslant 8$
On divise par $2$ :
$3 \leqslant \dfrac{u_{n} + 4}{2} \leqslant 4$
Or $u_{n+1} = \dfrac{u_{n} + 4}{2}$, donc $3 \leqslant u_{n+1} \leqslant 4$.
En particulier, $2 \leqslant u_{n+1} \leqslant 4$. Donc $P(n+1)$ est vraie.
Conclusion
D'après le principe de récurrence, pour tout $n \in \mathbb{N}$ : $2 \leqslant u_{n} \leqslant 4$.