Le raisonnement par récurrence - la rédaction

Le raisonnement par récurrence est une technique de preuve qui se voit en terminal. Un exposé des techniques liés, des preuves et de l'historique se trouve sur le wikipédia.

On considère $P(n)$ une proposition (assertion) qui dépend de $n \geq n_0$. On a :

Principe de récurrence : S'il existe $n_0\in \mathbb{N}$ tel que $P(n_0)$ soit vraie et tel que pour tout $n\in \mathbb{N}$ avec $n\geq n_0$, on ait $P(n)\Rightarrow P(n+1)$, alors $P(n)$ est vrai pour tout $n\in \mathbb{N}$ où $n\geq n_0$.

Ce principe est un théorème qui nécessite une preuve. Celle-ci est basée sur l'utilisation de l'axiome de Peano.

Une rédaction "universitaire" d'une preuve par récurrence est la suivante :

On considère $P(n)$ une proposition (assertion) qui dépend de $n \geq n_0$, où $n\in \mathbb{N}$.

Initialisation : Montrons que $P(n_0)$ est vraie.

On montre que $P(n_0)$ est vraie.

On a alors $P(n_0)$ est vraie.
Hérédité : Pour tout entier $n\geq n_0$, on montre que $P(n)\Rightarrow P(n+1)$.
Soit un entier $n\geq n_0$ fixe.
1) On suppose que $P(n)$ est fausse. On a alors que $P(n)\Rightarrow P(n+1)$.

2) On suppose que $P(n)$ est vraie. On montre (avec du travail) que $P(n+1)$ est vraie. On a donc que $P(n)\Rightarrow P(n+1)$.

Conclusion : Par récurrence, on a démontré que $P(n)$ est vraie pour tout $n\geq n_0$.

Au niveau universitaire, l'implication (mathématique) est "autorisée" mais cela n'est pas le cas en terminal et ce pose un soucis pour l'oral du concours de CAPES et pour le futur enseignement de ce concept. Certains livres de terminal propose des rédactions incorrectes. On consultera par exemple l'article de Denise Grenier intitulé : Une étude didactique du concept de récurrence.

En se rappelant le fait que pour avoir $P(n)\Rightarrow P(n+1)$ vraie, il suffit de démontrer que si $P(n)$ est vraie alors $P(n+1)$ est vraie (car si $P(n)$ est faux, l'implication est vraie), on peut obtenir une rédaction plus terminalesque.

Une rédaction "lycéenne" possible est d'une preuve par récurrence est donc la suivante :

On considère $P(n)$ une proposition (assertion) qui dépend de $n \geq n_0$, où $n\in \mathbb{N}$.

Initialisation : Montrons que $P(n_0)$ est vraie.

On montre que $P(n_0)$ est vraie.

On a alors $P(n_0)$ est vraie.
Hérédité : Pour tout entier $n\geq n_0$, on montre que si $P(n)$ est vraie alors $P(n+1)$ est vraie.

Soit un entier $n\geq n_0$ fixe. On suppose que $P(n)$ est vraie. On montre (avec du travail) que $P(n+1)$ est vraie.

La propriété $P(n)$ est héréditaire pour $n\geq n_0$.
Conclusion : Par récurrence, on a démontré que $P(n)$ est vraie pour tout $n\geq n_0$.

Mise en garde :

Ces rédactions semblent simples mais elles sont précises. Chaque mot a son poids. Il convient d'en apprendre une par coeur (au mot près...) et de ne pas s'en écarter.

Exercices :

• Exercices niveau terminal (non corrigés)
• Quelques exercices corrigés en ligne (avec vidéo !), niveau terminal.
• Activités à faire avec des élèves sous geogebra.