récurrence [latin : recurrere, courrir en arrière] (1)(T) :

Suite définie par récurrence (1)

Procédé consistant à définir une suite en donnant son premier terme, et une relation (dite relation de récurrence) permettant d'obtenir chaque terme à partir du précédent.

Les premiers termes de la suite définie par sont , , , etc...

Démonstration par récurrence (T)

Soit P(n) une proposition concernant les entiers naturels.

Démontrer P(n) par récurrence consiste à :

1) vérifier que P(0) est vraie (cette étape est appelée " initialisation ").
2) démontrer l'implication : pour n≥0, P(n)⇒P(n + 1) (cette étape est appelée "hérédité ").

Î

Il peut arriver qu'une propriété ne soit vraie qu'à partir d'un certain rang n₀ : Si :

1) P(n₀) est vraie et
2) Pour tout entier n≥n₀, P(n)⇒P(n+1),

Alors P(n) est vraie pour tout n≥n₀.