Les étapes

1
Initialisation
On énonce la propriété $P (n)$ P(n), puis on vérifie qu'elle est vraie au premier rang $n_{0}$ n₀ (calcul des deux côtés).
2
Hérédité
On suppose $P (n)$ P(n) vraie pour un $n$ n fixé (hypothèse), et on démontre $P (n + 1)$ P(n+1) en s'appuyant sur cette hypothèse.
3
Conclusion
On conclut par le principe de récurrence : $P (n)$ P(n) est vraie pour tout entier $n \geq n_{0}$ n ≥ n₀.

Exemple corrigé

Démontrer que pour tout entier $n \geq 1$ n ≥ 1, $1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}$ 1 + 2 + … + n = (n(n+1))/2.

1.Initialisation ( $n = 1$ n = 1) : à gauche $1$ 1, à droite $\frac{1 \times 2}{2} = 1$ (1× 2)/2 = 1. $P (1)$ P(1) est vraie.
2.Hérédité : on suppose $1 + \dots + n = \frac{n ( n + 1 )}{2}$ 1 + … + n = (n(n+1))/2. Alors $1 + \dots + n + (n + 1) = \frac{n ( n + 1 )}{2} + (n + 1) = \frac{n ( n + 1 ) + 2 ( n + 1 )}{2} = \frac{( n + 1 ) ( n + 2 )}{2}$ 1 + … + n + (n+1) = (n(n+1))/2 + (n+1) = (n(n+1) + 2(n+1))/2 = ((n+1)(n+2))/2.
3.C'est bien $P (n + 1)$ P(n+1). Conclusion : par récurrence, la formule est vraie pour tout $n \geq 1$ n ≥ 1.

Résultat :

1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}

1 + 2 + … + n = (n(n+1))/2 pour tout

n \geq 1

n ≥ 1.

Toujours rédiger les trois étapes, et bien faire apparaître l'hypothèse de récurrence dans l'hérédité.

Pour aller plus loin, explore les notions du même thème.

Raisonnement par récurrence, limites de suites, suites récurrentes et algorithmes de seuil.

Définitions, formules et exercices corrigés sur la même notion :