Download cours d`introduction

1.2 Principe de récurrence
Dans ce document, nous utiliserons fréquemment le principe de récurrence suivant.
Soit P (n) une propriété d’un entier n. On suppose que
(i) (initialisation) P (0) est vraie
(ii) (hérédité) pour tout entier naturel n, si P (n) est vraie alors P (n + 1) est vraie.
P(0)
P(1)
P(2)
P(3)
P(4)
Alors P (n) est vraie pour tout n.
Vocabulaire : lorsque l’on essaye de démontrer l’implication P (n) =⇒ P (n + 1), la
propriété P (n) que l’on suppose vraie s’appelle l’hypothèse de récurrence.
Une variante de ce principe est la récurrence forte : supposons que
(i) (initialisation) P (0) est vraie
(ii) (hérédité) pour tout entier naturel n, si P (k) est vraie pour tout k 6 n alors
P (n + 1) est vraie.
Alors P (n) est vraie pour tout n.
1.3 Mode d’emploi des exercices
Trois niveaux de difficultés (sans doute subjectifs) sont indiqués pour les exercices.
Les exercices non marqués sont des tests de compréhension immédiate, ou bien demandent
simplement d’appliquer une méthode indiquée quelques lignes plus haut.
Les exercices marqués avec le symbole ¶ peuvent demander une petite idée non évidente,
ou un peu de calcul.
Les exercices marqués avec ¶¶ nécessitent un temps de réflexion un peu plus long.
2