Raisonnement par récurrence

I- Introduction :
Le raisonnement par récurrence est utilisé pour montrer des résultats faisant intervenir une variable entière
de l’ensemble N ou d’une partie de cet ensemble, comme par exemple N , N
t1, 2u etc.
Cette démonstration s’effectue en trois étapes :

L’étape initialisation : Montrer que le résultat est vrai pour le tout premier rang (en général le premier
rang est 0, mais il se peut que le premier rang soit 1, 2 ou autre, cela dépend du résultat à démontrer).
L’étape hérédité : Montrer que le résultat est héréditaire, c’est-à-dire montrer que le résultat peut être
”transmis” d’un rang quelconque k au rang suivant k 1.
La conclusion
Pour expliquer ce principe assez intuitivement, prenons les deux exemples suivants :

Exemple 1 : La file de dominos

Si l’on pousse le premier domino de la file (Initialisation).
Et si les dominos sont posés l’un après l’autre d’une manière à ce que la chute d’un domino entraı̂ne la chute
de son suivant (Hérédité).
Alors : Tous les dominos de la file tombent. (la conclusion)

Exemple 2 : L’échelle
Si on sait monter le premier barreau de l’echelle (Initialisation).
Et si l’on sait toujours passer d’un barreau au barreau qui le suit (Hérédité).
Alors : On peut monter l’échelle. (la conclusion)
II- Énoncé :

Raisonnement par récurrence

Soit P pnq une propriété définie sur N. Si :

La propriété est initialisée à partir du premier rang n0 , c’est-à-dire :

P pn0 q est vraie.

Et la propriété est héréditaire, c’est-à-dire :

Pour un entier k quelconque, k ¥ n0 : P pk q ùñ P pk 1q.

Alors la propriété P pnq est vraie pour tout n ¥ n0

On commence par énoncer la propriété à démontrer, en précisant pour quels entiers naturels cette propriété
est définie, notamment le premier rang.
Il est fortement conseillé de toujours noter la propriété à démontrer P pnq, cela facilite grandement la rédaction
et nous évite des ambiguités.

Un raisonnement par récurrence se rédige en trois étapes :

1- On vérifie l’initialisation, c’est-à-dire que la propriété est vraie au premier rang (qui est souvent 0 ou 1).

2- On prouve le caractère héréditaire de la propriété, on suppose que la propriété est vraie pour un entier k
fixé et on démontre que la propriété est encore vraie au rang k 1.
Ici, on utilise toujours la propriété pour k pour montrer qu’elle est vraie aussi pour k 1
Il est conseillé de mettre dans un coin le résultat au rang k 1 à démontrer pour éviter des calculs fastidieux
inutiles.

Fiche issue de [Link] 1

3- On conclut en invoquant le principe de récurrence.

Pour ceux qui veulent aller plus loin (supérieur), cela peut s’écrire :

r loPomo
p0oqn et p nq p pn P N et P pnqq ñ P pn 1q q s ñ pnqpn P N ñ P pnqq
looooooooooooooooooooooomooooooooooooooooooooooon
initialisation hérédité

Concrètement dans les exercices, c’est la partie en bleu qu’on démontre et on conclut par la partie en rouge.
III-Exemples :
Exemple 1 :

Exercice :
Montrer par récurrence que :
npn 1q
Pour tout n P N : 0 1 2  n
2

Puisqu’il s’agit d’un premier exemple, on va détailler (peut-être trop) en expliquant chaque étape. Nous
exposerons ensuite une deuxième rédaction plus légère pour montrer comment bien rédiger un raisonnement
par récurrence.

Résolution étape par étape bien détaillée aux fins d’explication :

npn 1q
Il faut montrer par récurrence que pour tout n P N : 0 1 2  n
2
npn 1q
On pose pour cela : P pnq : 0 1 2    n 
2
Et puisqu’il s’agit des entiers n appartenant à N, le premier rang est 0 car il est le premier élément dans
l’ensemble N

0  p0 1q
1- Initialisation : Pour n  0 :
2
 0 2 1  0
Donc la proposition P p0q est vraie.

Remarques :
La somme 0 1 2    n veut dire qu’on additionne les nombres de 0 à n. Donc pour le cas n  0, on
0 et pas 0 1 2    0.
° qu’on
additionne les nombres de 0 à 0, ce qui implique que la somme vaut
On peut écrire les sommes en utilisant le symbole de la somme exposera après dans le paragraphe
suivant.

On n’écrit pas P p0q  0 car P pnq n’est pas un nombre qu’on calcule et on N’écrit PAS P pnq  0 1
npn 1q
2  n  .
2
P pnq est plutôt une proposition (”une phrase” mathématique) qui se lit : ” La somme 0 1 2    n est
npn 1q
égale à ”
2
2- Hérédité : Soit kP N un entier naturel.
k pk 1q
Supposons que P pk q : 0 1 2    k  est vraie, et montrons que dans ce cas, P pk 1q est
2
vraie.
Pour pouvoir démontrer une propriété mathématique, il faut tout d’abord la connaı̂tre. Dans notre cas, il
faut, avant de commencer, trouver ce qu’est l’expression de P pk 1q.
En général, on remplace tout simplement k dans l’expression de P pk q par k 1 pour trouver l’expression de
P pk 1q
P pk 1q : 0 1 2    pk 1q 
pk 1qrpk 1q 1s
2
On simplifie et on trouve : P pk 1q : 0 1 2    pk 1q 
pk 1qpk 2q
2

Fiche issue de [Link] 2

On va montrer que 0 1 2    pk 1q 
pk 1qpk 2q
à partir de P pk q : 0 1 2  k  kpk 2 1q
2

Pour ne pas se perdre, on écrit dans un coin :

k pk 1q
Hypothèse : P pk q : 0 1 2    k 
2
Résultat à prouver : P pk 1q : 0 1 2    pk 1q  pk 1qpk 2q
2
On sait que 0 1 2    pk 1q  0 1 2    k pk 1q car elle est la somme de 0 à k 1 et le
nombre qui précède k 1 est k.
Donc :
k pk 1q k pk 1q 2pk 1q
0 1 2    pk 1q  0 1 2  k
looooooooooomooooooooooon pk 1q 
2
pk 1q 
2

 p k k 1 q d’après la supposition
pk 1qpk 2q
2

Donc on a bien 0 1 2    pk 1q 
pk 1qpk 2q est donc P pk 1q est vraie
2
3- Conclusion :
On a vu que la propriété était vraie au rang 0 et qu’elle est héréditaire, donc elle est vraieau rang 1, donc au
rang 2...et de proche en proche elle est donc toujours vraie

npn 1q
Par récurrence, on obtient : Pour tout n P N : 0 1 2  n
2
Rédaction de la résolution :
npn 1q
Montrons par récurrence que pour tout n P N : 0 1 2  n
2
Notons pour cela : P pnq : 0    n  npn2 1q
1 2
0p0 1q
Initialisation : Pour n  0 :  0 , donc : P p0q est vraie
2
Hérédité : Soit k un entier naturel et supposons que P pk q est vraie.

k pk 1q
Hypothèse : P pk q : 0 1 2    k 
2
Résultat à prouver : P pk 1q : 0 1 2    k pk 1q 
pk 1qpk 2q
2
On a :
0 1 2    pk 1q  0 1 2  k pk 1q  kpk 2 1q pk 1q  kpk 1q
2
2pk 1q
 pk 1qpk
2
2q

On en déduit que P pk 1q est vraie.

npn 1q
On conclut par récurrence que : Pour tout n P N : 0 1 2  n Exemple 2 :
2

Exercice :
.

Montrer par récurrence que :

pour tout entier n ¥ 5 : 2n ¥ 6n
Montrons par récurrence que pour tout n ¥ 5 : 2n ¥ 6n
On pose : P pnq : 2n ¥ 6n "
Initialisation : Pour n  5 :
25  32
6  5  30 ¤ 32
Donc P p5q est vraie.
Hérédité : Soit k un entier naturel tel que k ¥ 5 et supposons que P pk q est vraie.
Montrons que P pk 1q est vraie.

Hypothèse : P pk q : 2k ¥ 6k
Résultat à prouver : P pk 1q : 2k 1
¥ 6pk 1q

Fiche issue de [Link] 3

2k 1  2  2k ¥ 2  6k  12k  6k 6k  6k 6k 6
6  6k 6 6k
6  6pk 1q 6pk

1q (En effet : on essaye de faire apparaı̂tre 6pk 1q )
Or, puisque k ¥ 5 alors k
1 ¥ 4 et 6pk
1q ¥ 24 ¥ 0
On en déduit 6pk 1q 6pk
1q ¥ 6pk 1q et il s’ensuit que 2k 1 ¥ 6pk 1q
P pk 1q est donc vraie.
On conclut par récurrence que : Pour tout n ¥ 5 : 2n ¥ 6n
Exemple 3 : Application aux suites

Prérequis : Les suites numériques

Exercice :
Soit une suite pUn q avec n P N définie par :
"
U0  7
Un 1  2Un 5

Montrer que pour tout n P N : 7 ¤ Un

Montrons par récurrence que pour tout n P N : 7 ¤ Un .

On pose P pnq : 7 ¤ Un
Initialisation : Pour n  0 on a : U0  7 ¥ 7
La proposition P p0q est vraie.
Hérédité : Soit k un entier naturel et supposons que P pk q est vraie.
Montrons que dans ce cas, P pk 1q l’est aussi.

Hypothèse : P pk q : 7 ¤ Uk
Résultat à prouver : P pk 1q : 7 ¤ Uk 1
On a 7 ¤ Uk
Donc 19 ¤ 2Uk 5
Donc 19 ¤ Uk 1
Or, puisque 7 ¤ 19 , on a : 7 ¤ Uk 1
Cela veut dire que P pk 1q est vraie.
° et produit ± :
On conclut par récurrence que : Pour tout entier n : Un ¥ 7 IV- Supplément : les symboles
somme
1- Symbole
°
Le symbole mathématique
°
permet d’exprimer plus simplement des sommes et donc des expressions
mathématiques, par exemple, la somme 0 1    10 peut s’écrire :

¸
10
0 1  10  k
k 0 
Ce terme se lit ”somme pour k allant de 0 à 10 de k”.
Cela signifie que l’on fait prendre au nombre k toutes les valeurs entières entre 0 et 10 et qu’on fait la somme
des nombres k :
On met la première valeur entière en bas du symbole, dans notre cas c’est 0.
On met la dernière valeur entière en haut du symbole sugma, ici c’est 10.
La lettre k est muette, elle ne sert qu’à compter et n’intervient pas dans le résultat final, on peut la rempla-
cer par n’importe quelle autre variable i, j,    (on évite l’utilisation des lettres déjà utilisées dans l’exercice) :

¸
10 ¸
10 ¸
10
k  i j

k 0 
i 0 
j 0
Prenons la somme du premier exemple du paragraphe précédent, on pouvait écrire :
ņ
k 0 1 2  n

k 0

Fiche issue de [Link] 4

 ¸
n 1
k 0 1 2  n pn 1q

k 0

Autres exemples :
3̧
1-
1
 1 1
1 2
1
3
6 3
6
2
 116
k1
k
ņ
2- 2p  p2  0q p2  1q p2  2q p2  3q    r2  pn
1qs p2  nq  0 2 4 6 8    2n

p 0
ņ
3- 2j 1  p2  0 1q p2  1 1q p2  2 1q p2  3 1q    r2  pn
1q 1s p2  n 1q 

   2n
j 0
1 3 5 7 1

Remarque : Dans l’exemple 1- , on ne pouvait pas débuter par k  0 car le dénominateur ne peut pas être
nul.
±
2- Symbole °
Comme son homologue pour les sommes, le symbole mathématique
± permet d’exprimer plus simplement
des produits, par exemple, le produit 1  2      10 peut s’écrire :

¹
10
1      10  k
k 1 
Exemples :
¹
4
p2k 1q  1  3  5  7  9  945

¹
k 0
n
k2  4  9      n2

¹
k 2
10
Remarquer que le produit présenté précédemment : k  1      10  10!

k 1

3- Exercice d’application :

Énoncé :
Montrer que :
 npn 1qp2n 1q
ņ
1- n P N : k2
k 0  6
ņ
2- n P N :  1
pn 1 1q!
k
k0
pk 1q!

Solution :
 npn 1qp2n 1q
ņ
1- Montrons par récurrence que n P N : k2 .

k 0
6

 npn 1qp2n 1q
ņ
Notons P pnq : k2

k 0
6
ņ
Il est conseillé d’écrire les termes avec sigma sous forme d’addition : k2  02 12 22  n2
$ 
¸0 2 2
k 0
'
' k 0 0
& k0
Initialisation : Pour n  0, on a :
'
'
% 0  p0 1qp2  0 1q  0
6
¸0 2 0  p0 1qp2  0 1q
Donc : k   0 et P p0q est vraie.

k 0
6

Fiche issue de [Link] 5

Hérédité :Soit p un entier de N, supposons que P ppq est vraie et montrons que P pp 1q est vraie (On évite
l’utilisation de la lettre k pour l’hérédité car déjà utilisée comme variable muette de la somme).
¸p
Hypothèse : P ppq : k2  ppp 1qp2p
6
1q

k 0
¸
 pp 1qpp 2qp2p 3q
p 1
Résultat à prouver : P pp 1q : k2

k 0
6
On a :

¸
p 1
k2  02 12    p2 pp 1q2

k 0  ¸p
 k2 pp 1q2
k 0 

 ppp 1qp2p
6
1q
pp 1q2

 ppp 1qp2p
6
1q 6pp 1q2

 pp 1qrpp2p
6
1q 6pp 1qs

 pp 1qp2p6 7p 6q
2

Or, on a : pp 2qp2p 3q  2p2 3p 4p 6  2p2 7p 6

p¸1
Donc : k2 
pp 1qp2p2 7p 6q  pp 1qpp 2qp2p 3q
k0
6 6
Cela veut dire que P pp 1q est vraie.

 npn 1qp2n 1q
ņ
On conclut par récurrence que : n P N : k2 .

k 0
6

ņ
2- Montrons par récurrence que n P N :  1
pn 1 1q!
k
k 0
pk 1q!
ņ
On note P pnq :  1
pn 1 1q!
k
k0
pk 1q!
ņ
Écriture de la somme sous forme d’addition :
pk 1q! p1 1q! p2 1q!
k
1q!
 p0 0 1 2
   pn n 1q!
$ k0̧0
'
'
& k0 pk 1q!  1!  1  0
k 0 0

Initialisation : Pour n  0, on calcule :

'
'
%1
1  1
1  1
1  0
p0 1q! 1!
¸0 k
pk 1q!  1
p0 1q!  0 et P p0q est vraie.
1
Donc :
k0
Hérédité :Soit m un entier de N, supposons que P pmq est vraie et montrons que P pm 1q est vraie.
m̧
Hypothèse : P pmq :  1
pm 1 1q!
k
k 0
pk 1q!
¸1 k
m
Résultat à prouver : P pm 1q :  1
pm 1 2q!
k0
p k 1q !
On a :

Fiche issue de [Link] 6

 ¸
m 1

pk
k
1q!
 p0 0 1q! p1 1 1q! p2 2 1q!    pm m 1q! pmm 1
2q!
k0  m̧
 p
k
1q ! p
m 1
2q!
k0
k m

 1
pm 1 1q! pmm 1
2q!

 1
pmm 2
2q!
m
pm
1
2q!
(En effet, en multipliant (m+1) ! par (m+2) on obtient (m+2) ! )

 1
m p
m2 2mq! 1

 1
pm 1 2q!

Il s’ensuit que P pm 1q est vraie.

ņ
Conclusion, par récurrence : n P N : pk
k
1q!
 1
pn 1 1q!
k0

Merci à Panter pour avoir contribué à l’élaboration de cette fiche

Fiche issue de [Link] 7