Nombresentiersnaturels –Combinatoire
COURS
9
1 Ensemble N.Récurrence
1.1 • Propriétésfondamentales de N
Nousa dmettrons l’existence d’un ensemble N ,n on vide, totalement ordonné,
vérifiant les propriétés suivantes :
N1:toute partie non vide de N aunplus petit élément.
N2:toute partie non vide majoréedeNaunplus grand élément.
N3:Nn’a pas de plus grand élément.
1.2 • Conséquences
Lespropriétés suivantes s’en déduisent immédiatement :
• N aunplus petit élément, noté 0.
• N\{0} aunplus petit élément, noté 1, etc.
On peut ainsi nommer les entiers naturels successifs.
• Pourtout n ∈ N, la partie {p ∈ N, p > n} aunplus petit élément appelé
successeur de n, et noté n +1.
On aainsi l’amorce de l’addition de N.
• Pour tout n ∈ N
∗
, la partie {p ∈ N, p < n} aunplus grand élément appelé
prédécesseur de n, et noté n − 1.
1.3 • Récurrence
Théorème 1(théorème de récurrence)
Soit P(n)u ne proposition dépendant d’un entier naturel n.
S’il existe un entier n 0 ∈ N telque :
1) P(n 0 )e st vraie ;
2) ∀n n 0 ,
P(n) ⇒ P(n +1)
,
alors P(n)e st vraie pour tout n n 0 .
Démonstration
Soit F l’ensemble desentiers n n 0 tels que P(n)s oit faux.
Il faut montrer que cet ensemble est vide.
Supposonsque F
= ∅ . Alors F aunplus petit élément n 1 ;d onc n 1 n 0
et P(n 1 )e st faux.
D’après 1), n 1 = n 0 , donc n 1 > n 0 , et n 1 − 1 n 0 .
Comme n 1 = min F , n 1 − 1 /
∈ F , donc P(n 1 − 1) estvraie, ce qui contredit
l’implication P(n 1 − 1) ⇒ P(n 1 ).
En définitive, F = ∅ ;d onc ∀n n 0 P(n)e st vraie.
 Hachette Livre –HPrépa /Math –Laphotocopie non autorisée est un délit
165