F.

HECHNER, ÉCÉ 2, Collège Épiscopal Saint Étienne Année 2014-2015

Fiche méthode 1 :
Le raisonnement par récurrence.
Le contexte : pour montrer qu’une propriété est vraie pour tout entier naturel (ou pour
tout entier plus grand qu’un entier fixé), on utilise très fréquemment un raisonnement par
récurrence.

1 Le principe de récurrence simple

1. Commencer par préciser les notations : notons, pour tout n ∈ N, P(n) le prédicat
suivant : “ . . . ”.
2. Vérifier que la propriété est vraie au rang 0 (ou pour un entier fixé). Autrement dit,
montrer que P(0) est vraie. On dit alors que la récurrence est initialisée.
3. Pour n entier naturel quelconque, montrer que si la propriété est vraie au rang n, alors
elle l’est aussi au rang n + 1. On dit alors que la récurrence est héréditaire : soit n ∈ N
fixé. Supposons P(n) vraie. Comme. . . . . . . . . , P(n + 1) est vraie.
4. Conclure : finalement, d’après le principe de récurrence, P(n) est vraie pour tout n ∈ N.

2 Le principe de récurrence double

Si la propriété P(n) au rang n dépend des propriétés aux rangs n − 1 et n − 2, on procède à
une récurrence double. Le principe est le suivant :
1. Commencer par préciser les notations : notons, pour tout n ∈ N, P(n) le prédicat
suivant : “. . . ”.
2. Vérifier que la propriété est vraie au rang 0 et au rang 1 (ou pour deux entiers consé-
cutifs fixés). Autrement dit, montrer que P(0) et P(1) sont vraies. On dit alors que la
récurrence est initialisée.
3. Pour n entier naturel quelconque, montrer que si la propriété est vraie au rang n et
au rang n + 1, alors elle l’est aussi au rang n + 2. On dit alors que la récurrence est
héréditaire : soit n ∈ N fixé. Supposons P(n) et P(n + 1) vraies. Comme. . . . . . . . . ,
P(n + 2) est vraie.
4. Conclure : finalement, d’après le principe de récurrence, P(n) est vraie pour tout n ∈ N.

3 Le principe de récurrence forte

Enfin, si la propriété P(n) au rang n dépend des propriétés à tous les rangs précédents, on
procède à une récurrence forte. Le principe est le suivant :
1. Commencer par préciser les notations : notons, pour tout n ∈ N, P(n) le prédicat
suivant : “. . . ”.

1/4
F. HECHNER, ÉCÉ 2, Collège Épiscopal Saint Étienne Année 2014-2015

2. Vérifier que la propriété est vraie au rang 0 (ou pour un entier fixé). Autrement dit,
montrer que P(0) est vraie. On dit alors que la récurrence est initialisée.
3. Pour n entier naturel quelconque, montrer que si la propriété est vraie jusqu’au rang n,
alors elle l’est aussi au rang n + 1. On dit alors que la récurrence est héréditaire : soit
n ∈ N fixé. Supposons P(0), . . . , P(n) vraies. Comme. . . . . . . . . , P(n + 1) est vraie.
4. Conclure : finalement, d’après le principe de récurrence, P(n) est vraie pour tout n ∈ N.

4 Exemples
4.1 Récurrence simple : premier exemple

Exercice 1 : n
Montrer que ∀n ∈ N, n(n+1)
.
P
k= 2
k=0

Solution :
n
Notons, pour tout n ∈ N, P(n) le prédicat : “ n(n+1)
”.
P
k= 2
k=0
0 0
• k = 0 et 0(0+1)
= 0, donc 0(0+1)
: P(0) est vraie. La récurrence est donc fondée.
P P
2
k= 2
k=0 k=0
• Soit n ∈ N fixé. Supposons P(n) vraie et montrons P(n + 1).
n+1
On veut donc montrer k = (n+1)(n+1+1) .
P
2
 n  k=0
n+1 n
Or k + (n + 1), et, par hypothèse de récurrence, k = n(n+1) , donc
P P P
k= 2
k=0  k=0
 k=0
n+1 n
k + (n + 1) = n(n+1) + (n + 1) = n(n+1)+2(n+1) = (n+2)(n+1) .
P P
k= 2 2 2
k=0 k=0
n+1
Comme (n+1)(n+1+1) (n+1)(n+2)
, on a bien (n+1)(n+1+1)
: P(n + 1) est vraie.
P
2
= 2
k= 2
k=0
La récurrence est donc héréditaire. n
• Finalement, d’après le principe de récurrence, ∀n ∈ N, n(n+1)
.
P
k= 2
k=0

4.2 Récurrence simple : deuxième exemple

Exercice 2 :
On considère la suite (un ) définie par u0 := 1 et ∀n ∈ N, un+1 := un e−un .
Montrer que ∀n ∈ N, un ∈ [0, 1].

Solution :

2/4
F. HECHNER, ÉCÉ 2, Collège Épiscopal Saint Étienne Année 2014-2015

Montrons, par récurrence sur n ∈ N, le prédicat P(n) : “un ∈ [0, 1]”.

• Comme u0 = 1 ∈ [0, 1], P(0) est vraie.
• Soit n ∈ N fixé. Supposons P(n) vraie. Alors 0 6 un 6 1, donc 0 > −un > −1 et, par
croissance de la fonction exponentielle, e0 > e−un > e−1 , qui s’écrit encore 1e 6 e−un 6 1. En
multipliant les différents membres de cet encadrement par un qui est positif par hypothèse
de récurrence, on a donc uen 6 un e−un 6 un . Comme par hypothèse de récurrence 0 6 un et
un 6 1, on en déduit 0 6 uen 6 un e−un 6 un 6 1. Enfin, comme un+1 = un e−un , on obtient
bien 0 6 un+1 6 1 : P(n + 1) est vraie.
• D’après le principe de récurrence, ∀n ∈ N, un ∈ [0, 1] .

4.3 Récurrence simple : troisième exemple

Exercice 3 :
Montrer que pour tout entier n, 2n
6 4n .


n

Solution :

Rappelons que 2n (2n!)

= (2n!) .


n
= n!(2n−n)! n!n!
Montrons, par récurrence sur n ∈ N, le prédicat P(n) : “ 2n 6 4n ”.


n
• Comme 00 = 1 et que 40 = 1 également, le prédicat est vrai au rang 0.

• Soit n ∈ N fixé. Supposons P(n) vrai. Écrivons

 
2(n + 1) (2n + 2)! (2n + 2)!
= =
n+1 (n + 1)!(2(n + 1) − (n + 1))! (n + 1)!2
 
(2n + 2)(2n + 1).(2n)! (2n + 2)(2n + 1) 2n
= =
(n + 1)2 n!2 (n + 1)2 n
   
2(n + 1).2(n + 1) 2n 2n
= 2 =4 6 4.4n = 4n+1
(n + 1) n n

donc le prédicat est vrai au rang n + 1.

• Le prédicat est fondé et héréditaire, donc d’après le principe de récurrence, P(n) est vrai
pour tout n ∈ N : ∀n ∈ N, n 6 4 .
2n

n

4.4 Récurrence double : un exemple

Exercice 4 :
On considère la suite (un ) définie par u0 := 3, u1 := 5 et ∀n ∈ N, un+2 = 3un+1 − 2un .
Montrer que ∀n ∈ N, un = 2n+1 + 1.

Solution :

Montrons, par récurrence double sur n, le prédicat P(n) : “un = 2n+1 + 1”.

3/4
F. HECHNER, ÉCÉ 2, Collège Épiscopal Saint Étienne Année 2014-2015

• Comme 20+1 + 1 = 3 = u0 , P(0) est vraie. De même, comme 21+1 + 1 = 5 = u1 , P(1) est
vraie. La récurrence est initialisée.
• Soit n ∈ N fixé. Supposons P(n) et P(n + 1) vraies, et montrons P(n + 2).
Comme P(n) est vraie, un = 2n+1 +1. Comme P(n+1) est vraie, un+1 = 2n+1+1 +1 = 2n+2 +1.
Alors, d’après la définition de un+2 , un+2 = 3un+1 − 2un = 3 (2n+2 + 1) − 2 (2n+1 + 1) =
3 × 2n+2 + 3 − 2 × 2n+1 − 2 = 3 × 2n+2 − 2n+2 + 1 = 2 × 2n+2 + 1 = 2n+2+1 + 1, donc P(n + 2)
est vraie.
• D’après le principe de récurrence, ∀n ∈ N, un = 2n+1 + 1 .

4.5 Récurrence forte : un exemple (idiot ?)

Exercice 5 : n
On considère la suite (un ) définie par u0 := 1 et ∀n ∈ N, un+1 := uk . Montrer que
P
k=0
∀n ∈ N∗ , un = 2n−1 .

Solution :

Montrons, par récurrence forte sur n > 1, le prédicat P(n) : “un = 2n−1 ”.
0
• Comme 21−1 = 20 = 1 et que u1 = u0 = u0 = 1, on en déduit que u1 = 21−1 , donc P(1)
P
k=0
est vraie.
• Soit n ∈ N∗ fixé. Supposons P(1), . . . , P(n) vraies et montrons P(n + 1).
n
Par définition, un+1 = uk .
P
k=0
n n n
D’après l’hypothèse de récurrence, 2k−1 .
P P P
uk = u0 + uk = 1 +
k=0 k=1 k=1
n−1
En effectuant le changement d’indice j = k − 1 dans la somme, on a un+1 = 1 + 2j .
P
j=0
On reconnaît la somme des termes d’une suite géométrique de raison 2, donc :
n−1
P j 1−2n
2 = 1−2 = 2n − 1.
k=0
n−1
Ainsi, un+1 = 1 + 2j = 1 + 2n − 1 = 2n = 2(n+1)−1 . On en déduit que P(n + 1) est vraie.
P
j=0
• Finalement, d’après le principe de récurrence, ∀n ∈ N∗ , un = 2n−1 .
n
P n−1
P
Il aurait sans doute ici été plus malin de remarquer que un+1 = uk = uk +un = un +un = 2un ,
k=0 k=0
donc (un ) est géométrique de raison 2.

4/4