Travaux Dirigés : Raisonnement par récurrence
1 La démonstration par récurrence
Lorsqu’une propriété est vraie pour tout entier naturel ou pour tout entier au-delà d’un entier donné, le raisonne-
ment par récurrence est l’un des outils à envisager systématiquement pour sa démonstration.
Principe de la démonstration par récurrence
Soit à démontrer :
∀n ∈ [[n0 , +∞[[ P(n) où P est une propriété dépendant de l’entier naturel n.
La démonstration par récurrence consiste à :
1. vérifier que la propriété est vraie pour la valeur n0 : c’est l’initialisation de la récurrence.
2. puis vérifier que si la propriété est vraie pour un certain n (fixé quelconque), alors la propriété est vraie au rang
suivant n + 1.
Autrement dit, P(n) ⇒ P(n + 1) pour n entier fixé quelconque (la propriété est dite héréditaire).
ALORS, on peut conclure que pour tout n ≥ n0 , la propriété P(n) est vraie.
Attention : la propriété à démontrer doit être complètement et précisémment énoncée.
L’image des dominos : Imaginez - devant vous - une infinité de dominos placés l’un après l’autre et verticalement.
On sait de plus que :
– le premier domino est en train de tomber
– au vu de la distance entre deux dominos, si le nie domino tombe alors le suivant (le n + 1e ) tombera.
Qu’en déduit-on ?
Exemple : Montrer que ∀n ∈ N, 2n ≥ n + 1.
On pose P(n) : ”2n ≥ n + 1”.
– Initialisation de la récurrence : cas n = 0.
20 = 1 ≥ 0 + 1 donc P(0) est vraie.
– Hérédité : Supposons que P(n) soit vraie pour un certain n ; on a donc 2n ≥ n + 1.
Nous devons prouver que (pour ce n) P(n + 1) est vraie, c’est-à-dire que 2n+1 ≥ (n + 1) + 1 = n + 2.
Mais 2n+1 = 2 × 2n donc comme par hypothèse de récurrence, on a 2n ≥ n + 1 et que 2 ≥ 0,
on obtient 2 × 2n ≥ 2(n + 1) soit 2n+1 ≥ 2n + 2.
Or 2n + 2 − (n + 2) = n ≥ 0 donc 2n + 2 ≥ n + 2.
Par conséquent 2n+1 ≥ 2n + 2 ≥ n + 2, ce qui démontre que P(n + 1) est vraie.
– Conclusion : P(n) est vraie pour tout entier n positif.
Exercice 1:
n 1 n
1. Montrer par récurrence que ∀n ∈ N∗ ,
P
= .
k=1 k(k + 1) n + 1
n n(n + 1)
2. Montrer par récurrence que ∀n ∈ N∗ :
P
k=
k=1 2
(preuve à retenir car plus facile que celle vue dans le TD sur le symbole somme)
Point fort de ce raisonnement par récurrence : il est très facile à mettre en place.
Point faible de ce raisonnement : il constate l’exactitude d’un résultat préalablement proposé mais ne l’établit pas.
Dans certains exercices, la recherche de la solution pourra consister à proposer un résultat (en analysant la propriété
pour des petites valeurs de n) puis à démontrer ce résultat par récurrence.
2 Deux formes particulières de la démonstration par récurrence
2.1 Récurrence double
La démonstration par récurrence double consiste à :
1. vérifier que la propriété est vraie pour les deux premiers rangs
2. puis vérifier que si n est un entier quelconque tel que la propriété est vraie aux rangs n ET n + 1
alors elle est vraie au rang n + 2
Alors la propriété est vraie pour tout n.
Remarque
Cette forme de récurrence est particulièrement utile pour vérifier des propriétés sur certaines suites.
Exercice 2:
Soit (un )n∈N la suite numérique définie par
u0 = 2 et u1 = 3
∀n ∈ N, un+2 = 3un+1 − 2un
Vérifier que : ∀n ∈ N, un = 1 + 2n
2.2 Récurrence forte
La démonstration par récurrence forte consiste à :
1. vérifier que la propriété est vraie pour le premier rang,
2. puis vérifier que si n est un entier quelconque tel que la propriété est vraie jusqu’au rang n (c’est-à-dire que la
propriété est vraie pour tout k ≤ n), alors elle est vraie au rang n + 1.
Alors la propriété est vraie pour tout n.
Exercice 3:
Soit (un )n∈N la suite définie par
u0 = 1
n
P
∀n ∈ N, un+1 = uk
k=0
Vérifier que : ∀n ∈ N∗ , un = 2n−1
Exercices supplémentaires :
Exercice 4:
Montrer par récurrence :
n
(2k − 1) = n2 (somme des n premiers entiers impairs)
P
1. ∀n ≥ 1,
k=1
n 1 − q n+1
qk =
P
2. ∀n ≥ 0,
k=0 1−q
n n(n + 1)(2n + 1)
k2 =
P
3. ∀n ≥ 0,
k=0 6
n
3 1
4. ∀n ≥ 15, ≤ ( )n
n! 2
Exercice 5:
On considère une suite u telle que ∀n ≥ 0, un+1 ≤ a × un où a est un réel positif.
Montrer par récurrence que ∀n ≥ 0, un ≤ an u0 .