L'idée : les dominos
Imaginez une rangée de dominos, aussi longue que vous voulez. Pour être sûr qu'ils tombent tous, il suffit de vérifier deux choses :
- le premier domino tombe ;
- chaque fois qu'un domino tombe, il fait tomber le suivant.
Alors tous les dominos tombent, même le millionième. C'est exactement l'idée du raisonnement par récurrence : le domino numéro , c'est l'affirmation , une propriété qui dépend de l'entier .
La méthode en 3 étapes
Sur une copie, on rédige donc en 3 étapes, après avoir écrit la propriété :
- Initialisation : on vérifie que est vraie.
- Hérédité : on montre que, pour tout entier , si est vraie, alors est vraie.
- Conclusion : par récurrence, est vraie pour tout entier .
Dans l'hérédité, on fixe un entier quelconque, on suppose que est vraie (c'est l'hypothèse de récurrence, notée HR), et on démontre . Comme est quelconque, le raisonnement vaut pour chaque domino.
Les deux pièges
Exemples corrigés
Exemple 1 Une somme de nombres impairs
Montrer que pour tout entier : .
Pour tout , notons : « ».
Initialisation. Pour : le membre de gauche vaut , et . est vraie.
Hérédité. Soit fixé. On suppose (HR) : . Le nombre impair suivant est . Donc est vraie.
Conclusion. Par récurrence, pour tout , .
Exemple 2 Une suite définie par récurrence
Soit et, pour tout , . Montrer que pour tout : .
Pour tout , notons : « ».
Initialisation. . est vraie.
Hérédité. Soit fixé. On suppose (HR) : . Alors (On a utilisé .) est vraie.
Conclusion. Par récurrence, pour tout , .
Le réflexe : on part de , on applique la définition de la suite, puis l'hypothèse de récurrence.
Exemple 3 Type bac
Soit et, pour tout , . Montrer que pour tout : .
Pour tout , notons : « ».
Initialisation. et . On a bien : est vraie.
Hérédité. Soit fixé. On suppose (HR) : . On veut : .
On multiplie par , qui est positif, donc le sens des inégalités ne change pas : On ajoute 1 : Comme , on obtient .
Conclusion. Par récurrence, pour tout , . En bonus : la suite est croissante et majorée par 2.
Exercices corrigés
Exercice 1 Divisibilité
Montrer que pour tout , est divisible par 3.
Coup de pouce : .
Voir la correction
Pour tout , notons : « est divisible par 3 ».
Initialisation. : divisible par 3. est vraie.
Hérédité. Soit fixé. On suppose (HR) : , avec entier. Donc , et est un entier : est divisible par 3.
Conclusion. Par récurrence, pour tout , est divisible par 3.
Exercice 2 Une inégalité
Montrer que pour tout : .
Coup de pouce : multiplier l'hypothèse de récurrence par 2.
Voir la correction
Pour tout , notons : « ».
Initialisation. . est vraie.
Hérédité. Soit fixé. On suppose (HR) : . En multipliant par : On veut . Or , car . Donc .
Conclusion. Par récurrence, pour tout , .
À retenir
Questions fréquentes
Comment rédiger l'hérédité d'une récurrence ?
On écrit : « Soit un entier fixé. Supposons que est vraie. » Puis on démontre en utilisant cette hypothèse. Il est utile d'écrire d'abord ce qu'on veut obtenir, , pour savoir où l'on va.
Peut-on commencer une récurrence à n = 1 au lieu de n = 0 ?
Oui, ou à tout autre entier . On initialise au premier rang où la propriété doit être vraie, et la conclusion vaut alors pour tout .
Pourquoi l'initialisation est-elle obligatoire ?
Parce que l'hérédité seule ne prouve rien : elle dit seulement « si un domino tombe, le suivant tombe ». La propriété « est divisible par 9 » est héréditaire, mais fausse pour tout .