Suites et récurrence/Démonstration par récurrence
Le raisonnement par récurrence permet de démontrer une propriété concernant des entiers naturels
(il ne fonctionne pas sur d'autres types de nombres).
Principe de récurrence
[modifier | modifier le wikicode]Soient une propriété dépendant de l'entier naturel
- et un entier naturel.
Si :
- est vraie ;
- pour tout entier tel que est vraie, on a vraie
Alors, pour tout entier , est vraie.
Rédaction
[modifier | modifier le wikicode]On a vu que le principe de récurrence prend appui sur deux points. Il faut donc montrer ces deux points puis invoquer le principe de récurrence. Tout raisonnement par récurrence suit alors trois étapes :
- Initialisation : on vérifie que est vraie.
- Hérédité : on suppose que est vraie, où est un entier supérieur ou égal à . Cette supposition est l'hypothèse de récurrence.
- On montre alors à partir de cette hypothèse que est vraie.
- Conclusion : l'axiome de récurrence permet de conclure que est vraie pour tout entier .
Exemples
[modifier | modifier le wikicode]Soit la suite définie pour tout entier naturel par : .
Montrer par récurrence que est minorée par 1.
Soit la propriété " ".
- Initialisation: .
- Hérédité: supposons que . On pose .
Alors (comme ) on a : donc soit . Donc et la propriété est héréditaire.
- Conclusion: est bien minorée par 1.
Démontrer par récurrence que pour tout entier naturel n on a :
- .
Tout d’abord, on énonce la propriété à démontrer. Dans notre cas, on veut montrer que pour tout entier (donc à partir de ) :
- .
On pose pour tout la propriété la proposition « ».
On procède ensuite à la première étape : l'initialisation.
- Initialisation
- Comme , la proposition est vraie.
Ensuite, montrons l'hérédité
- Hérédité
- Soit tel que soit vraie.
- Montrons que est également vraie.
- Dans notre exemple, montrer que est vraie consiste à montrer que en sachant que est vraie, c'est-à-dire que
- Allons-y :
- .
- On utilise l'hypothèse de récurrence :
- Donc est vraie.
- Conclusion
Pour terminer, on conclut avec l'invocation du principe de récurrence :
Le principe de récurrence permet de conclure que : .