Raisonnement par récurrence

Soit P un prédicat concernant un paramètre entier n.
P(n) vrai signifie donc : "n possède la propriété n".

On suppose que:

P(0) est vrai
et que de plus ∀n P(n) ⇒ P(n+1), c'est à dire que P(n+1) est vrai dès que P(n) est vrai.

Il s'en suit que:

P(1) est vrai puisque P(0) l'est
que P(2) est vrai puisque P(1) l'est
et ainsi de suite de proche en proche.

On en conclut que P(n) est vrai ∀ n ∈

.
C'est le principe même du 'raisonnement par récurrence' sous sa forme la plus simple.

Il y a, bien sûr quelques variantes:
Evidemment si au lieu de P(0) vrai on sait seulement que P(n₀) est vrai on a seulement:
P(n) vrai pour n ≥ n₀.
Si on sait que P(0) est vrai et que ∀n P(n) ⇒ P(n+2), on en conclut que P(n) est vrai pour n pair
Si on sait que P(1) est vrai et que ∀n P(n) ⇒ P(n+2), on en conclut que P(n) est vrai pour n impair
Si on sait que P(0) et P(1) sont vrais et que ∀n P(n) ⇒ P(n+2), on en conclut que P(n) est vrai pour tout n .

On peut aussi faire une récurrence sur

.
Si P(0) est vrai, si ∀n P(n) ⇒ P(n+1) et ∀n P(n) ⇒ P(n-1), on en conclut que P(n) est vrai ∀ n ∈

On a aussi des formes de 'récurrence multiple'.

Soit au niveau de l'hypothèse de récurrence:

Supposons que P(0) et P(1) soient vrais
et que ∀ n P(n) ∧ P(n-1) ⇒ P(n+1)

Alors ∀ n P(n) est vrai.

Soit au niveau du nombre des variables:

Supposons que cette fois P(m,n) soit une propriété des couples d'entiers
Supposons que P(0,0) soit vrai
Supposons que ∀ m,n P(n,m) ⇒ P(n+1,m)
Supposons que ∀ m,n P(n,m) ⇒ P(n,m+1)

Alors P(m,n) est vrai ∀ (m,n) ∈

On a enfin la 'récurrence forte'

Supposons que P(0) soit vrai
Supposons que si( ∀ p ≤ n P(n)) ⇒ P(n+1)

Alors P(n) est vrai ∀ n.

Voir les exercices de ce paragraphe pour des exemples.

Nous avons déjà vu des exemples de raisonnement par récurrence:
Nombre de parties d'un ensemble
Relation entre les coefficients Cp,n

Le point faible de toutes les formes de raisonnement par récurrence est qu'ils vérifient des propriétés, mais qu'ils ne les établissent pas directement. On ne peut pas trouver par récurrence un résultat dont on n'a a priori aucune idée. Ce qui fait qu'en pratique on est obligé, quand on ne connaît pas le résultat de traiter 'manuellement' un grand nombre de petites valeurs de la variable pour avoir une idée de la loi. C'est seulement après ce travail, disons d'intuition, que le raisonnement par récurrence viendra conforter le chercheur dans sa conviction.