COURS 9
Nombresentiers naturels –Combinatoire
APPLICATION 1
Démontrer que ∀n 4, n
2
2
n
.
1) La propriété estv érifiée pour n = 4, car
4
2
= 2
4
= 16.
2) Soit n 4t el que n
2
2
n
.
En multipliantpar 2les deux membres, on en déduit :
2n
2
2
n+1
.
Comparons( n+1)
2
et 2n
2
:
(n +1)
2
−2n
2
=−n
2
+2n+1.
Ce trinôme admet pour racines 1−
√ 2e t1 +
√ 2; il
estpositif entre les racines, c’est-à-dire pour les entiers
0, 1, 2etnégatif au delà, c’est-à-dire pour tout entier
supérieur ou égal à3.
Ici n 4, donc (n +1)
2
2n
2
2
n +1
:l a
proposition estvérifiée pour n +1.
Le théorème de récurrence permet de conclure que
∀n 4 n
2
2
n
.
Cet exemple est instructif, car la proposition P(2)
est vraie, mais on ne peut pas choisir n 0 = 2, car
l’implication P(n) ⇒ P(n +1)n ’est pas vraie pour
n = 2. On ne peut pas non plus choisir n 0 = 3,
car P(3) estfausse... Le premier entier qui satisfait les
deux hypothèses du théorème est donc n 0 = 4.
Pours’entraîner :ex. 2à4
Dans certains cas, il peut être nécessaire de regrouper dans l’hypothèse de récurrence
plusieurs niveauxsuccessifs de la proposition P ;p ar exemple (P(n)e tP ( n +1)).
Il fautalors démontrer que :
1) P(n 0 )e tP ( n 0 +1)s ont vraies ;
2) ∀n n 0
P(n)etP(n+1)
⇒ P(n+2);
pour conclure que ∀n n 0 , P(n)e st vraie.
Pour s’entraîner:ex. 5
On peutmême regrouper dans l’hypothèse de récurrence tous les niveaux jusqu’à
n (récurrence forte). Il faut alors démontrer que :
1) P(n 0 )e st vraie ;
2) ∀n n 0
∀p ∈ [[ n 0 , n ]] P ( p )
⇒ P ( n +1);
pour conclure que ∀n n 0 , P(n)e st vraie.
APPLICATION 2
Démontrerque tout entier n ∈ N
∗
peut s’écrire de façon
unique sous la forme: n=2
p
(2q +1), où (p, q) ∈ N.
1) 1 = 2
0
(2 × 0+1); la proposition estvérifiée pour
n = 1.
2) Soit n ∈ N
∗
tel que tout entier de 1à n puisse
s’écrire de la façonindiquée.
a) Si n +1 est impair :
∃q ∈ N n +1=2
0
(2q +1)
b) Si n +1 estp air,
n +1
2
est un entier compris
entre1et n ;i lvérifie l’hypothèse de récurrence :
∃(p, q) ∈ N
2 n +1
2
=2
p
(2q +1)
d’où :
n +1=2
p +1
(2q +1).
La proposition estencore vérifiée pour n +1.
L’existence de la décomposition est donc établie pour
tout n ∈ N
∗
.
166
Nombresentiers naturels –Combinatoire
APPLICATION 1
Démontrer que ∀n 4, n
2
2
n
.
1) La propriété estv érifiée pour n = 4, car
4
2
= 2
4
= 16.
2) Soit n 4t el que n
2
2
n
.
En multipliantpar 2les deux membres, on en déduit :
2n
2
2
n+1
.
Comparons( n+1)
2
et 2n
2
:
(n +1)
2
−2n
2
=−n
2
+2n+1.
Ce trinôme admet pour racines 1−
√ 2e t1 +
√ 2; il
estpositif entre les racines, c’est-à-dire pour les entiers
0, 1, 2etnégatif au delà, c’est-à-dire pour tout entier
supérieur ou égal à3.
Ici n 4, donc (n +1)
2
2n
2
2
n +1
:l a
proposition estvérifiée pour n +1.
Le théorème de récurrence permet de conclure que
∀n 4 n
2
2
n
.
Cet exemple est instructif, car la proposition P(2)
est vraie, mais on ne peut pas choisir n 0 = 2, car
l’implication P(n) ⇒ P(n +1)n ’est pas vraie pour
n = 2. On ne peut pas non plus choisir n 0 = 3,
car P(3) estfausse... Le premier entier qui satisfait les
deux hypothèses du théorème est donc n 0 = 4.
Pours’entraîner :ex. 2à4
Dans certains cas, il peut être nécessaire de regrouper dans l’hypothèse de récurrence
plusieurs niveauxsuccessifs de la proposition P ;p ar exemple (P(n)e tP ( n +1)).
Il fautalors démontrer que :
1) P(n 0 )e tP ( n 0 +1)s ont vraies ;
2) ∀n n 0
P(n)etP(n+1)
⇒ P(n+2);
pour conclure que ∀n n 0 , P(n)e st vraie.
Pour s’entraîner:ex. 5
On peutmême regrouper dans l’hypothèse de récurrence tous les niveaux jusqu’à
n (récurrence forte). Il faut alors démontrer que :
1) P(n 0 )e st vraie ;
2) ∀n n 0
∀p ∈ [[ n 0 , n ]] P ( p )
⇒ P ( n +1);
pour conclure que ∀n n 0 , P(n)e st vraie.
APPLICATION 2
Démontrerque tout entier n ∈ N
∗
peut s’écrire de façon
unique sous la forme: n=2
p
(2q +1), où (p, q) ∈ N.
1) 1 = 2
0
(2 × 0+1); la proposition estvérifiée pour
n = 1.
2) Soit n ∈ N
∗
tel que tout entier de 1à n puisse
s’écrire de la façonindiquée.
a) Si n +1 est impair :
∃q ∈ N n +1=2
0
(2q +1)
b) Si n +1 estp air,
n +1
2
est un entier compris
entre1et n ;i lvérifie l’hypothèse de récurrence :
∃(p, q) ∈ N
2 n +1
2
=2
p
(2q +1)
d’où :
n +1=2
p +1
(2q +1).
La proposition estencore vérifiée pour n +1.
L’existence de la décomposition est donc établie pour
tout n ∈ N
∗
.
166