Qu’est-ce qu’une démonstration par récurrence ?

Réponse courte

Une récurrence prouve qu’une proposition P(n) est vraie pour tous les entiers n à partir d’un rang n₀ : on vérifie P(n₀), puis on montre que, pour chaque n ≥ n₀, P(n) entraîne P(n + 1).

Comprendre

Le point de départ

On choisit la proposition P(n) et le premier entier n₀ visé. L’initialisation consiste à vérifier réellement P(n₀). Ce rang dépend de l’énoncé : il peut être zéro, un ou une autre valeur.

Le passage au rang suivant

Pour l’hérédité, on fixe un entier n ≥ n₀ et on suppose P(n) vraie. À partir de cette hypothèse, on établit P(n + 1), sans la supposer. Si ces deux étapes sont prouvées, alors P(n₀) entraîne P(n₀ + 1), puis les rangs suivants : P(n) est vraie pour tout n ≥ n₀.

Exemple d’une somme

Pour démontrer 1 + 3 + … + (2n − 1) = n² pour n ≥ 1, l’initialisation donne 1 = 1². Au passage, si la somme vaut n², le terme suivant est 2n + 1 : la nouvelle somme vaut n² + 2n + 1 = (n + 1)². L’égalité est donc établie à chaque rang. Une récurrence ne se réduit pas à constater quelques cas : elle justifie le mécanisme qui transmet la propriété.

Étapes

  1. Énonce P(n) et le premier rang n₀ visé.
  2. Vérifie P(n₀) par un calcul adapté.
  3. Fixe n ≥ n₀, suppose P(n), puis démontre P(n + 1).
  4. Conclue pour tous les entiers n ≥ n₀ par récurrence.

Exemples

  • Pour P(n) : 1 + 3 + … + (2n − 1) = n², P(1) devient 1 = 1².
  • Si P(n) donne une somme égale à n², ajouter 2n + 1 donne n² + 2n + 1 = (n + 1)².

Pièges fréquents

  • Vérifier P(1) ne prouve que le premier cas : sans l’implication de P(n) vers P(n + 1), rien ne garantit les rangs suivants.
  • Dans l’hérédité, supposer directement P(n + 1) serait circulaire ; seule P(n) est admise provisoirement.

Pourquoi ça marche

L’initialisation démarre la chaîne des cas vrais et l’hérédité relie chaque maillon au suivant.

Et maintenant ?

Questions proches

← Toutes les questions-réponses