Récurrence

Un article de Wiki SILLAGES.

Ce résumé est basé sur le programme de mathématiques de première année des classes préparatoires aux grandes écoles économiques et commerciales, voie scientifique (ECS1). Un résumé complet du programme de mathématiques ECS1 est proposé sur la Plate-forme SILLAGES.

Sommaire

1 Premier théorème de récurrence
- 1.1 Conseils de rédaction d’une récurrence
2 Deuxième théorème de récurrence (récurrence forte)
- 2.1 Conseils de rédaction

Premier théorème de récurrence

Soit $P(n)$ une propriété définie pour tout entier $n\geq n_0$ .

Si les deux conditions suivantes sont vérifiées :

1) Initialisation : $P(n_0)$ est vraie.

2) Hérédité : Chaque fois que $P(n)$ est vraie pour $n\geq n_0$ , alors $P(n+1)$ est vraie.

Alors $P(n)$ est vraie pour tout entier $n\geq n_0$ .

Conseils de rédaction d’une récurrence

Bien définir la propriété $P(n)$ .

Initialisation : Déterminer le premier entier $n_0$ et démontrer que $P(n_0)$ est vraie.

Hérédité : Supposer que $P(n)$ est vraie pour un entier $n\geq n_0$ et démontrer que (pour ce $n$ ) $P(n + 1)$ est vraie.

Conclusion : En appliquant le théorème, conclure que $P(n)$ est vraie pour tout entier $n\geq n_0$ .

Deuxième théorème de récurrence (récurrence forte)

Soit $P(n)$ une propriété définie pour tout entier $n\geq n_0$ .

Si les deux conditions suivantes sont vérifiées :

1) Initialisation : $P(n_0)$ est vraie.

2) Hérédité : Chaque fois que (pour un entier $n\geq n_0$ ) $P(k)$ est vraie jusqu'à $n$ (c'est à dire pour tout entier $k$ tel que $n_0\leq k\leq n$ ), alors $P(n+1)$ est vraie.

Alors $P(n)$ est vraie pour tout entier $n\geq n_0$ .

Conseils de rédaction

Hérédité: Supposer que $P(n_0)$ , $P(n_0 +1)$ , ..., $P(n)$ sont vraies pour un entier $n\geq n_0$ et démontrer que (pour ce $n$ ) $P(n + 1)$ est vraie.