Que se passe-t-il si l’initialisation manque dans une preuve par récurrence ?

Réponse courte

Sans initialisation, la récurrence ne démarre pas : l’hérédité transmettrait une propriété déjà vraie à un rang, mais ne prouverait pas qu’elle l’est au premier rang visé. La conclusion annoncée n’est donc pas établie.

Comprendre

Une transmission sans départ

L’hérédité prouve seulement une implication : si P(n) est vraie, alors P(n + 1) l’est. Elle ne garantit pas qu’il existe un rang où P(n) est vraie. Il faut vérifier P(n₀), le premier rang du domaine, avant de pouvoir transmettre la propriété.

Un exemple qui montre le défaut

Considère P(n) : n ≥ 1 pour les entiers n ≥ 0. Si P(n) est vraie, alors n + 1 ≥ 2, donc P(n + 1) est vraie : l’hérédité fonctionne. Pourtant P(0) est fausse. Conclure « P(n) pour tout n ≥ 0 » serait erroné, car la chaîne n’a jamais été amorcée au rang zéro.

Reprendre une preuve incomplète

Identifie le domaine annoncé, puis calcule P(n₀) avec les valeurs exactes. Pour l’égalité 1 + 3 + … + (2n − 1) = n², commencer à n = 1 donne bien 1 = 1². Si l’énoncé fixe ce domaine n ≥ 1, une initialisation à n = 0 ne remplace pas le contrôle de n = 1. Une initialisation à un rang supérieur ne permet pas de conclure pour les rangs qui le précèdent.

Étapes

  1. Repère le premier rang n₀ demandé par l’énoncé.
  2. Évalue P(n₀) sans utiliser l’hérédité.
  3. Si P(n₀) échoue, corrige la proposition ou restreins le domaine avec justification.
  4. Ne conclus qu’à partir du premier rang effectivement initialisé.

Exemples

  • Pour P(n) : n ≥ 1 sur n ≥ 0, P(0) est fausse alors que P(n) entraîne P(n + 1).
  • Pour la somme des n premiers impairs, le rang 1 donne 1 = 1² et sert de départ pour les rangs n ≥ 1.

Pièges fréquents

  • Présenter une hérédité correcte comme preuve complète oublie que l’implication ne dit pas que son hypothèse est vraie au départ.
  • Initialiser au rang 2 puis conclure pour tout n ≥ 0 étend la conclusion à des rangs qui n’ont pas été prouvés.

Pourquoi ça marche

L’implication transmet une vérité ; elle ne crée pas le premier cas vrai nécessaire au démarrage.

Et maintenant ?

Questions proches

← Toutes les questions-réponses