Correction d'une récurrence

Je présente maintenant une correction commentée d'un calcul de la somme des $n$ premiers entiers par récurrence. 

---

Tout d'abord il est crucial de préciser pour quels $n$ on travaille. 

Pour la proposition $P(n)$, deux points. On l'annonce avec $:=$ afin d'insister que nous avons à faire à une définition. Puis on l'encadre avec des guillemets pour bien délimiter sa définition. La proposition $P(n)$ une phrase qui est ou vraie ou fausse. Ici on remarque la structure minimale d'une phrase : sujet, verbe, complément.

---

On montre maintenant l'étape d'initialisation. Ici on se heurte de plein fouet au problème de la notation avec 3 petits points de la somme. 

---

Ici deux rédactions de la partie hérédité sont proposées.

---

On conclue la récurrence en termes de $P(n)$ mais aussi en reformulant le problème sous sa forme originelle.

Quelques rédactions de récurrences à éviter

Voici la rédaction (avant leçon complète) de quatre étudiants. L'exercice demandait de démontrer la formule donnant la somme des $n$ premiers entiers.

---

Ici, l'erreur la plus grosse est de ne par définir la propriété $P(n)$ que l'on cherche à démontrer. On introduit aussi un $u_n$ qui est inutile. La rédaction de la conclusion demande des petits ajustements.  $P(n)$ devrait être $(P(n))_n$ par exemple.

---

Ici le choix est de faire une rédaction sans l'utilisation de $P(n)$. Cela est bien-sûr possible tant que les propositions se sont pas trop complexe.

On trouve le choix d'utiliser "un certain" au lieu de pour tout. Bien que correct il est plus compliqué d'expliquer qu'il correspond à un "pour tout" et non pas à un "il existe" auprès de lycéens.

Il y aussi un problème "d'esthétisme". Les barres des fractions doivent être au niveau du milieu du signe égal. 

---

Ici il y a surtout un manque de rédaction. Il est important de conclure chaque étape pour la rendre plus lisible. La proposition $P(n)$ n'est pas donnée non plus.

---

Ici nous avons (enfin) la proposition $P(n)$ qui fait son apparition. On remarquera que le quantificateur $\forall$ est à sa bonne place (et non pas dans les guillemets...). On regrettera une rédaction plus légère (non structuration en Initialisation/Hérédité/Conclusion). Il y a aussi une confusion entre le mode de démonstration "universitaire" (avec l'utilisation d'un implique dans la phase d'hérédité) et celui "lycéen" qui est annoncé au début (on suppose que $P(n)$ vrai, montrons que $P(n+1)$ vrai...). 

Enfin ici on remarquera un mélange des genres. La partie hérédité est traitée en tant que récurrence forte et la conclusion ne le mentionne pas.

---

Cette rédaction est bonne. On pourrait lui reprocher le fait que le texte soit trop fourni. Dans l'esprit de l'écris du concours du CAPES, une rédaction plus condensée est à prévoir si un nombre important de récurrence est à produire. 

---

Ici il y a une erreur grave dans la rédaction de l'hérédité. L'étudiant suppose que $P(n)$ est vrai pour tout $n$ et donc c'est automatiquement vrai pour $n+1$... et il n'y a rien à démontrer. Une façon de procéder est de rajouter "un certain" (voir commentaire au dessus pour son utilisation). Mais il est préférable de mettre "Soit $n\in \mathbb{N}$ quelconque. On suppose que $P(n)$ est vrai. Montrons que $P(n+1)$ vrai.

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.