#13
Principe de récurrence
Khôlles - Classes prépa Thierry Sageaux, Lycée Gustave Eiel.
Exercice 1.
Montrer par récurrence les propriétés suivantes (dire à chaque fois quel type de récurrence vous
utilisez) :
n Montrer que un = 2n − 1.
1) k = n(n+1) .
P
k=0
2 6) Pour tout n ∈ N et pour tout x ∈ [0, +∞[,
2) 32n − 2n est divisible par 7. on a (1 + x)n≥ 1 + nx.
n u =2
3) Montrer que pp! = (n + 1)! − 1. 7) On pose u 0 = √u .
P
p=0 n+1 n
n Montrer que 1 ≤ un ≤ 2 pour tout n ∈ N.
4) 2 n(n+1)(2n+1)
. 8) Montrer que n! > 3n à partir d'un certain
P
k = 6
rang.
k=0
si n ≥ 1
un+1 = 2un + 1
5) On pose . 9) Pour tout nombre entier n, il existe un pre-
u1 = 1.
mier p qui le divise.
Exercice 2.
n 1 n
Montrer par récurrence puis avec une DES que ∀n ∈ N\{0}, on a .
P
=
k=1 k(k + 1) n + 1
Exercice 3. √ √ √ √ √ √ √ √ √ √
On remarque que (1 + 2) = 1 + 2, (1 + 2)2 = 3 + 2 2 = 8 + 9, (1√+ 2)3√= 49√+ 50.
Le but est de démontrer que pour tout n ∈ N∗ , il existe αn ∈ N tel que (1 + 2)n = αn + αn + 1.
1) Montrer qu'il existe deux entiers an et bn tel que
√ √
(1 + √2)n = an + bn √2
.
(1 − 2)n = an − bn 2
2) Etablir alors que a2n − 2b2n = (−1)n et en déduire le résultat attendu.
Exercice 4.
Soit (un ) la suite dé nie par u0 = 2, u1 = 7 et u?n+2 = 7un+1 − 10un .
Montrer que un = 2n + 5n .
Exercice 5.
n
Soit (Sn ) la suite dé nie par S0 = 1 et ∀n ∈ N, Sn+1 = Sk .
P
k=0
Montrer que ∀n ∈ N\{0}, on a sn = 2n−1 .
Exercice 6.
Comparer 2n et n2 pour diérentes valeurs de n. Résoudre 2n2 ≥ (n + 1)2 .
Déterminer par récurrence si 2n ≥ n2 pour tout n > 3.
Exercice 7.
1) Soit Sn la somme des n premiers naturels impairs.
a) Calculer S1 , S2 et S3 .
b) Montrer que Sn = n2 par récurrence, puis directement.
c) Trouver une démonstration géométrique, sans aucun calcul de cette égalité.
2) Soit Tn la somme des cubes des n premiers entiers naturels impairs.
29 janvier 2017 1 Thierry Sageaux
Principe de récurrence
a) Montrer que Tn = 2n4 − n2 .
b) Déterminer n tel que Tn = 29161.
Exercice 8.
On pose Pn : "9 divise 10n − 1" et Qn : "9 divise 10n + 1". Montrer que ces deux propriétés sont
héréditaires. Sont-elles vraies pour tout n ?
Exercice 9.
Montrer la formule du binôme de Newton.
Exercice 10. Le piège classique.
Trouver ce qui ne va pas dans le raisonnement par récurrence suivant :
Pn : " Dans un groupe de n chevaux, ils sont tous de la même couleur."
Initialisation : La propriété P1 est vraie car un cheval tout seul a la même couleur que lui-même.
Hérédité : Supposons la propriété Pp vraie pour p xé.
Montrons alors que Pp+1 est [Link] Pp est vraie,
tout groupe de p chevaux ont la même couleur. On
en prend au hasard p + 1 que l'on met dans un pré
(voir dessin ci-contre). Le sous-ensemble A contient p
chevaux qui sont de la même couleur. Idem pour le
sous-ensemble B . Ainsi tout l'ensemble a la même cou-
leur.
Conclusion : Pn est vraie pour tout n et tous les chevaux
ont la même couleur.
2 Thierry Sageaux
Principe de récurrence
Solutions des exercices
Exercice 3.
1) Séparer les indices pairs des impairs.
2) Distinguer deux cas selon parité.
Exercice 7.
2) a) Par récurrence. (Hn ) : ”Tn = 2n4 − n2 ”.
Initialisation : (H1 ) est vraie car T1 = 1 = 2 × 14 − 12 .
Hérédité : On suppose (Hn ) vraie pour n xé. On remarque que
n
(2k − 1)3 .
P
Tn =
k=1
Donc
n+1
X
Tn+1 = (2k − 1)3 = Tn + (2(n + 1) − 1)3 = (2n4 − n2 + (2n + 1)3
k=1
= 2n4 + 8n3 + 11n2 + 6n + 1 = (n + 1)2 (2n2 + 4n + 1)
= (n + 1)2 (2(n + 1)2 − 1) = 2(n + 1)4 − (n + 1)2 .
Donc (Hn+1 ) est vraie et la propriété est héréditaire.
Conclusion : Elle est initialisée au rang 1, elle est héréditaire, elle est donc vraie pour tout n
entier naturel non nul.
b) n = 11
3 Thierry Sageaux