On emploie le raisonnement par récurrence pour démontrer des propriétés parfois élaborées, qui font intervenir des entiers. Il faut souvent un peu d’intuition (ou une grande habitude) pour savoir s’il est indispensable de raisonner par récurrence ou si une preuve directe est possible.

Une rédaction soignée

Il est important d’apprendre à bien rédiger :

• Annonce de la démonstration par récurrence avec l’énoncé de la propriété , et le champ des valeurs de l’entier (pour tout )
• Initialisation : est vraie
• Hérédité : Pour tout fixé, , implique . On doit voir clairement dans cette partie à quel moment on utilise l’hypothèse de récurrence.
• Conclusion

Si vous suivez bien ces consignes, vous êtes en mesure d’aborder des récurrences plus sophistiquées (récurrence sur deux termes, ou récurrence avec prédécesseurs,…). Il est conseillé, dans les cas difficiles, de bien constater que votre récurrence « tourne ».

Des erreurs à ne pas commettre

En voici quelques exemples :

1. Vous posez bien votre démonstration, avec l’initialisation, mais à l’étape « hérédité » vous arrivez à démontrer sans utiliser l’hypothèse de récurrence : cela signifie que la récurrence était inutile et que vous pouviez faire une démonstration « directe ».

2. Vous démontrez en utilisant mais aussi : ce n’est pas possible avec une récurrence ordinaire. Il faut poser soit une récurrence sur deux termes (avec aussi l’initialisation sur deux termes), soit une récurrence avec prédécesseurs. Cet accident arrive souvent dans les problèmes sur certaines suites () ou sur les familles de polynômes (polynômes de Tchebychev, par exemple, ).

3. Vous oubliez l’initialisation.
Soit : est multiple de 7
Vous pouvez démontrer facilement l’hérédité de cette propriété.
Testez numériquement à la calculatrice : vous voyez que n’est pas vraie pour …. Quelle conclusion peut-on donner ?
Si vous savez manipuler les congruences (ici modulo 7), vous pouvez démontrer que est fausse pour tout .

4. Vous initialisez à un mauvais rang.
Soit : dans une assemblée de n personnes, tout le monde porte le même prénom.
est vraie de manière évidente. Supposons vraie et soit une assemblée de personnes. Isolons une personne et considérons l’ensemble des autres personnes : toutes ont le même prénom d’après l’hypothèse de récurrence. Réintégrons la personne isolée et faisons sortir du groupe une autre personne : nous avons à nouveau un ensemble de n personnes qui ont donc toutes le même prénom. Et finalement toute l’assemblée a bien le même prénom. La propriété est héréditaire, initialisée, donc vraie pour tout .
Cherchez l’erreur…

Principe, axiome ou théorème ?

La présentation qu’on fait aux étudiants de la démonstration par récurrence sème une certaine confusion sur l’origine de ce raisonnement. Certains professeurs disent « principe de récurrence », d’autres « axiome de récurrence », d’autres encore « théorème de récurrence ». De quoi s’agit-il donc ? Je vous en dirai davantage lors d’un prochain billet