Raisonnement par récurrence
Histoire des mathématiques :
Al-Karaji est un mathématicien et ingénieur d’origine persane du Xème siècle, principalement installé à
Bagdad (actuel Irak). On connait peu de choses de sa vie, mais on sait qu’il est l’auteur de traités d’algèbre et
de géométrie, ainsi que de travaux d’hydrologie. Ses talents en algèbre lui valent le surnom de « calculateur ».
Il est le 1er à utiliser implicitement le raisonnement dit « par récurrence », qui sera formalisé des siècles plus
tard par l’italien Giuseppe Peano et le français Blaise Pascal.
Muhammad Al-Karaji 953-1029 Blaise Pascal 1623-1662 Giuseppe Peano 1858-1932
Lien vidéo cours : https://www.youtube.com/watch?v=MJv7_pkFcdA
1. Illustration :
Question : quelles sont les deux conditions pour que tous les dominos se renversent ?
Réponse : on renverse le 1er domino et on s’assure que chaque domino renverse le suivant.
2. Axiome de récurrence :
Pour démontrer par récurrence qu’une propriété Pnest vraie pour tout entier naturel
n ≥ n0 fixé , on procède en 3 étapes :
1ère étape : initialisation
On vérifie que Pn est vraie, c’est-à-dire que la propriété est vraie pour le 1er indice n 0 .
0
2ème étape : hérédité
On suppose que pour un entier n quelconque (n ≥ n0 ), la propriété Pn est vraie et sous cette
hypothèse, dite de récurrence, on démontre que la propriété Pn +1est vraie.
On a ainsi prouvé que l’hypothèse de récurrence « Pnest vraie » est héréditaire.
3ème étape : conclusion
Lorsque les 2 étapes ont été réalisées, on conclut que la propriété Pnest vraie pour tout entier
naturel n(n ≥n 0).
Raisonnement par récurrence 1
3. Comment démontrer par récurrence :
Exemple 1 : capacités 1 page 13, 9 page 136
2 n (n+1)(2 n+1)
Démontrer que pour tout n ∈ N ¿ ,12 +22 +32 +¿ …………..+ n = .
6
2 n (n+1)(2 n+1)
Soit Pnla propriété : 12 +22 +32 +¿ …………..+ n = pour tout entier n ∈ N ¿.
6
1 étape : initialisation
ère
2 n(n+1)(2 n+1) 1 ×2 ×3 1 ×2 ×3
Pour n=1:1 =1et = =1 donc 1 2=
6 6 6
Donc la propriété est vraie pour n=1
2ème étape : hérédité
Soit n un entier naturel non nul quelconque.
On suppose que la propriété Pnest vraie, montrons que la propriété Pn +1est vraie,
2 n (n+1)(2 n+1)
On sait que 12 +22 +32 +¿ …………..+ n = .
6
( n+1 )( n+ 1+ 1 ) ( 2 ( n+1 )+1 )
On veut montrer que 12 +22 +32 +¿ …………..+ n2 + ( n+ 1 )2=
6
(n+1)(n+ 2)(2 n+3)
¿ .
6
2 2 n ( n+1 )( 2 n+1 )
1 +2 +3 +¿ …………..+ n + ( n+ 1 ) =
2 2 2
+ ( n+1 )2
6
n ( n+1 ) ( 2n+ 1 )+ 6(n+1)²
¿
6
( n+1 ) [n ( 2 n+1 ) +6 ( n+1 ) ]
¿
6
2
( n+1 ) (2 n +7 n+6)
¿
6
2
(n+1)(n+ 2)(2 n+3) (2 n¿¿ 2+3 n+ 4 n+ 6) (n+1)(2n +7 n+6)
Or =( n+1 ) = ¿
6 6 6
2 2 (n+1)(n+2)(2 n+3)
Par conséquent 12 +22 +32 +¿ …………..+ n + ( n+ 1 ) =
6
3 étape : conclusion
ème
La propriété Pnest vraie pour n=1 et est héréditaire à partir du rang 1, donc d’après le principe de
récurrence, la propriété Pnest vraie pour tout entier n> 0, c’est-à-dire :
2 n (n+1)(2 n+1)
Pour tout entier naturel n ∈ N ¿ ,12 +22 +32 +¿ …………..+ n =
6
Exemple 2 :
Démontrer par récurrence que, pour tout entier naturel n ≥ 3 :2n> 2 n.
Soit Pnla propriété : 2n >2 npour tout entier n ≥ 3.
1ère étape : initialisation
Pour n=3 :23=8 et 2× 3=6 donc 23 >2 ×3donc la propriété est vraie pour n=3.
2ème étape : hérédité
Soit n un entier quelconque, n ≥ 3.
On suppose que la propriété Pnest vraie, montrons que la propriété Pn +1est vraie.
On sait que : 2n >2 n .
On veut montrer que : 2n +1> 2(n+1).
Raisonnement par récurrence 2
On en déduit : 2 ×2n >2 ×2 n ⇔2 n+1 >4 n .
On compare alors 4 n et 2 ( n+1 ) .
4 n−2 ( n+1 )=2 n−2
Or n ≥ 3 donc 2 n ≥ 6 donc 2 n−2≥ 4 >0
Donc 2n +1> 4 n> 2(n+1)
La propriété est vraie au rang n+1.
3ème étape : conclusion
La propriété Pn est vraie pour n=3 et est héréditaire à partir du rang 3, donc d’après le principe de
récurrence, la propriété Pnest vraie pour tout entier n ≥ 3, c’est-à-dire :
Pour tout entier naturel n ≥ 3 :2n> 2 n.
Exemple 3 : inégalité de Bernouilli (démonstration exigible)
Soit un nombre réel a positif.
Pour tout entier naturel n , on a : ( 1+a )n ≥ 1+na.
Soit Pnla propriété : ( 1+a )n ≥ 1+na pour tout entier n .
Initialisation :
Pour n=0 : ( 1+a )0 =1 et 1+0 × a=1: la propriété est vraie pour n=0.
Hérédité :
Soit n un entier quelconque.
On suppose que la propriété Pnest vraie, montrons que la propriété Pn +1est vraie.
On sait que : ( 1+a )n ≥ 1+na
On veut montrer que : ( 1+a )n+1 ≥1+(n+1)a
Donc : ( 1+a )( 1+a )n ≥ ( 1+a )( 1+na )
( 1+a )n+1 ≥1+na+ a+n a 2
( 1+a )n+1 ≥1+ ( n+ 1 ) a+ n a ² ≥ 1+ ( n+1 ) a, car n a 2 ≥ 0.
Donc : ( 1+a )n+1 ≥1+ ( n+ 1 ) a .
Conclusion :
La propriété est vraie pour n=0et héréditaire à partir de ce rang. D'après le principe de récurrence, elle est
vraie pour tout entier naturel n soit : ( 1+a )n ≥ 1+na.
Lien vidéo :
https://www.youtube.com/watch?v=H6XJ2tB1_fg&ab_channel=YvanMonka
Liens vidéo :
https://www.youtube.com/watch?v=udGGlHdSAgc&ab_channel=YvanMonka
https://www.youtube.com/watch?v=OIUi3MG8efY&ab_channel=YvanMonka
https://www.youtube.com/watch?v=nMnLaE2RAGk&ab_channel=YvanMonka
https://www.youtube.com/watch?v=LXSJB0BnPD4&ab_channel=YvanMonka
Raisonnement par récurrence 3
