Démontrer une propriété par récurrence
Savoir énoncer le principe de récurrence et l'appliquer pour démontrer qu'une propriété P(n) est vraie pour tout entier n ≥ n₀.

Les points essentiels
- Le principe de récurrence permet de démontrer qu'une propriété P(n) est vraie pour tout entier n à partir d'un rang de départ n₀.
- Une démonstration par récurrence comporte deux étapes obligatoires : l'initialisation et l'hérédité.
Les mots à connaître
- Principe de récurrence
- Soit P(n) une propriété qui dépend d'un entier n, et n₀ un entier naturel. Si P(n₀) est vraie et si, pour tout entier k ≥ n₀, P(k) entraîne P(k+1), alors P(n) est vraie pour tout entier n ≥ n₀.
- Initialisation
- Étape de la démonstration où l'on vérifie directement que la propriété P est vraie au rang de départ n₀.
Un exemple pour comprendre
Démontrer que pour tout entier n ≥ 1, la somme 1 + 2 + ⋯ + n vaut n(n+1)/2.
On note P(n) la propriété : 1 + 2 + ⋯ + n = n(n+1)/2 pour tout entier n ≥ 1. Initialisation. Pour n = 1, le membre de gauche vaut 1 et le membre de droite vaut 1(1+1)/2 = 1. Les deux membres sont égaux, donc P(1) est vraie. Hérédité. Soit k un entier fixé avec k ≥ 1. On suppose P(k) vraie : 1 + 2 + ⋯ + k = k(k+1)/2. On veut montrer P(k+1) : 1 + 2 + ⋯ + k + (k+1) = (k+1)(k+2)/2. On calcule la somme jusqu'au rang k+1 : 1 + 2 + ⋯ + k + (k+1) = [1 + 2 + ⋯ + k] + (k+1) = k(k+1)/2 + (k+1). On met au même dénominateur : k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2. On obtient bien P(k+1). Conclusion. D'après le principe de récurrence, P(n) est vraie pour tout entier n ≥ 1.

