NOTION Le-raisonnement-par-récurrence

Le 20-03-2019

Les suites

Le raisonnement par récurrence
Rappel
Notation d’une suite
• « (un ) » avec les parenthèses désigne la suite
• « un » sans les parenthèses désigne le terme
de rang n.
• On peut définir une suite par une fonction :
un = f (n).
• Ou par récurrence :  un+1 = f (un ).
Rappel
Suites arithmétiques et suites géométriques
• Les suites arithmétiques sont de la forme :
– un+1 = un + r ;
– ou un = u0 + r × n.
• Les suites géométriques sont de la forme :
– un+1 = un × q ;
– ou un = u0 × q n .
Définition
Raisonnement par récurrence
Le raisonnement par récurrence vise à démontrer
de proche en proche une propriété P (n) d’une
suite, à partir du rang n0 .

Les étapes sont les

suivantes :
• Initialisation : on montre que P (n0 ) est
vraie.
• Hérédité : on choisit un entier n ≥ n0 . On
suppose que P (n) est vraie (hypothèse de
récurrence), et on s’en sert pour montrer que
P (n + 1) est vraie.
• Conclusion : on en déduit que P (n) est vraie
pour tout n ≥ n0.
Exemple
Soit (un ) la suite définie par u0 = 0 et un+1 =
2un + 1. On cherche à démontrer par récurrence
la propriété P (n) selon laquelle un = 2n − 1, pour
tout entier naturel n.
• Initialisation : u0 = 0 et 20 − 1 = 1 − 1 = 0.
Donc P (0) est vraie.
• Héréditié : soit k un entier naturel.
– On suppose que P (k) est vraie. Donc
uk = 2k − 1.
– Or l’énoncé dit que uk+1 = 2uk + 1.
– Donc uk+1 = 2×(2k −1)+1 = 2k+1 −2+1 =
2k+1 − 1. Donc P (k + 1) est vraie.
• Conclusion

:

d’après

le

principe

de

récurrence, P (n) est vraie pour tout entier
naturel n.
Remarque
Attention : une propriété peut être héréditaire,
sans être vraie, si l’initialisation n’est pas vérifiée
!

Il ne faut donc jamais oublier d’initialiser le

raisonnement par récurrence.