Récurrence

Un article de wiki sillages.info.

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

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.


--CatherineLaidebeure 19 juillet 2010 à 15:33 (CEST)