Initialisation et hérédité

Le problème que résout la récurrence

Comment démontrer qu'une propriété P(n) est vraie pour TOUS les entiers naturels n à partir d'un certain rang, alors qu'il y en a une infinité ? On ne peut évidemment pas vérifier chaque cas un par un. Le raisonnement par récurrence répond à ce problème en deux étapes seulement.

Les deux étapes obligatoires

Principe de recurrence pour une propriete P(n) :

Etape 1 - INITIALISATION
  On verifie que P(n0) est vraie          (n0 = le premier rang, souvent 0 ou 1)

Etape 2 - HEREDITE
  On suppose P(k) vraie pour un k >= n0   (hypothese de recurrence)
  On demontre alors que P(k+1) est vraie  (le pas suivant)

CONCLUSION : P(n) est vraie pour tout n >= n0

Pourquoi ces deux étapes suffisent

L'initialisation donne un point de départ solide (P(n0) est vraie). L'hérédité montre que la vérité se transmet automatiquement d'un rang au suivant, quel que soit ce rang. En combinant les deux : P(n0) est vraie, donc P(n0+1) est vraie (par hérédité), donc P(n0+2) est vraie, et ainsi de suite indéfiniment. La propriété se propage à l'infini sans qu'on ait besoin de la vérifier rang par rang.

Ce qu'il faut bien comprendre dans l'hérédité

L'étape d'hérédité ne démontre PAS que P(k) est vraie : elle démontre seulement une implication, "SI P(k) est vraie ALORS P(k+1) est vraie". C'est une différence essentielle : on ne suppose jamais que la propriété est vraie en général, seulement qu'elle l'est à UN rang k fixé, pour en déduire le rang suivant.

Piège classique

Les deux étapes sont indispensables : l'hérédité seule, sans initialisation vérifiée, ne prouve rien du tout (voir la leçon sur les erreurs classiques). Une implication "P(k) vraie implique P(k+1) vraie" peut être parfaitement correcte et pourtant ne partir d'aucune vérité initiale, auquel cas elle ne démontre absolument rien sur les entiers réels.