Raisonnement par récurrence
Maths Terminale
Définition
Le raisonnement par récurrence sert à démontrer qu'une propriété $P(n)$ est vraie pour tout entier $n \ge n_0$. Il repose sur deux étapes : l'initialisation (montrer que $P(n_0)$ est vraie) et l'hérédité (supposer $P(n)$ vraie pour un entier $n$ quelconque, puis montrer que $P(n+1)$ l'est aussi). Si ces deux étapes sont vérifiées, alors $P(n)$ est vraie pour tout $n \ge n_0$.
Formule
$$\big(P(n_0)\ \text{vraie}\big)\ \text{et}\ \big(\forall n \ge n_0,\ P(n) \Rightarrow P(n+1)\big) \implies \forall n \ge n_0,\ P(n)\ \text{vraie}$$
Exemple corrigé
Énoncé
Démontrer par récurrence que, pour tout entier $n \ge 1$, $\;1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$.
Solution
Soit $P(n)$ : $\;1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$.
Initialisation ($n=1$) : à gauche $1$ ; à droite $\dfrac{1\times 2}{2} = 1$. Donc $P(1)$ est vraie.
Hérédité : supposons $P(n)$ vraie pour un entier $n \ge 1$, c'est-à-dire $1+2+\cdots+n = \dfrac{n(n+1)}{2}$. Montrons $P(n+1)$.
$$1+2+\cdots+n+(n+1) = \frac{n(n+1)}{2} + (n+1)$$
$$= (n+1)\left(\frac{n}{2} + 1\right) = (n+1)\cdot\frac{n+2}{2} = \frac{(n+1)(n+2)}{2}.$$
C'est bien la formule au rang $n+1$. Donc $P(n+1)$ est vraie.
Conclusion : par récurrence, $\boxed{\;1+2+\cdots+n = \dfrac{n(n+1)}{2}\;}$ pour tout $n \ge 1$.
Erreurs classiques
- Oublier l'initialisation : l'hérédité seule ne prouve rien si aucun rang de départ n'est vérifié.
- Dans l'hérédité, utiliser ce qu'on veut démontrer ($P(n+1)$) comme s'il était déjà acquis, au lieu de partir uniquement de l'hypothèse $P(n)$.
Pour aller plus loin : le chapitre « Suites : limites et raisonnement par récurrence » (cours et exercices corrigés).