Terminale · Mathématiques

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₀.

Aperçu gratuit
Illustration de la fiche « Démontrer une propriété par récurrence »

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.

Première page de l’Essentiel : Démontrer une propriété par récurrence
Ketty