Le raisonnement par récurrence

Fin du XVIIIe siècle. La légende raconte qu’un professeur imposa à ses élèves l’exercice ingrat de calculer la somme des entiers naturels (c’est-à-dire supérieurs ou égaux à $0$ ) inférieurs à $100$ , pensant ainsi les occuper pendant un moment. Mais, au bout de quelques instants, il remarqua que l’un d’eux s’ennuyait. Quelle ne fut pas sa surprise lorsque ce dernier lui annonça le résultat : $5050$ . Le nom de cet élève ? Carl Friedrich Gauss.

Carl Friedrich Gauss — Tableau de Gauss par Gottlieb Biermann (1887),
d’après un portrait par Christian Albrecht Jensen (1840).

Le petit Gauss, du haut de ses neuf ans, décida de réfléchir au problème plutôt que de foncer tête baissée dans le calcul. Il remarqua une identité intéressante :

100 + 1 = 99 + 2 = 98 + 3 = \ldots = 50 + 51 = 101.

Il en conclut immédiatement la valeur de la somme recherchée :

0 + 1 + 2 + \ldots + 100 = (1 + 100) + (2 + 99) + \ldots + (50 + 51) = \dfrac{100}{2} \cdot 101 = 5050.

Ce résultat se généralise en fait à toutes les sommes de $0$ à $n$ , où $n$ est un entier naturel¹. On peut le démontrer avec un raisonnement dit par récurrence.

Dans ce tutoriel, nous vous introduisons à cette méthode de démonstration très utilisée en Mathématiques² et en donnons des exemples d’applications qui vous permettront de pratiquer. Le contenu se veut accessible au plus grand nombre mais il est néanmoins nécessaire de connaître la notion de preuve (ou démonstration) et il est recommandé d’être à l’aise avec celles d’énoncé logique, d’implication et de suites.

Si $n = 0$ , la somme est simplement nulle.
↩
Elle était déjà parfaitement maîtrisée au XVIIe siècle, par Pascal, Fermat et Bernoulli notamment.
↩

Le principe de récurrence

Le tutoriel n’est pas fini, deux parties restent à publier :

« Pratiquons » comportera des exercices pour assimiler les concepts par l’expérience ;
« Pour aller plus loin » fournira des détails mathématiques supplémentaires et présentera des types de récurrences plus exotiques.

Les auteurs remercient vivement @adri1 pour la validation et @oddocda pour les retours en bêta.

7 commentaires

Ge0, lundi 14 janvier 2019 à 12h20

Le début du tutoriel est bien fait et à raison de pratique, j’estime pouvoir en saisir tous les concepts.

Je me demandais si l’un de vous avait des resources de choix en ce qui concerne les preuves / démonstrations, avec des exercices si possibles ? C’est la partie dans laquelle je me sens le moins à l’aise.

Aussi, je trouve super d’expliquer en français les terminologies mathématiques telles que $\sum$ ou $\forall$ qui ne sont pas forcément acquises de tout le monde.

14/01/19 à 12h20

Ge0

+0 -0

Karnaj, dimanche 23 juin 2019 à 22h13

@Ge0 je remarque que ton commentaire est passé sous silence, je ne me souviens pas du tout l’avoir lu et là je tombe dessus par hasard. Tu chercherais des preuves et des exercices de quel niveau ? Y a par exemple plein d’exercices en combinatoire qui peuvent se faire par récurrence (même si je trouve que c’est plus élégant de le faire de manière ensembliste).

23/06/19 à 22h13

Assez des salamis, je passe au jambon — Je fais un carnage si ce car nage car je nage, moi, Karnaj ! — Le comble pour un professeur de mathématique ? Mourir dans l’exercice de ses fonctions.

+0 -0

Ge0, lundi 24 juin 2019 à 12h36

Merci beaucoup pour ton retour Karnaj (aucun problème pour le délai).

Je cherche surtout des exercices de classe préparatoire, d’un point de vue d’autodidacte qui souhaite se (re)mettre dans le bain.

24/06/19 à 12h36

Ge0

+0 -0

Karnaj, lundi 24 juin 2019 à 13h24

Voici quelques exemples de trucs qu’on peut prouver par récurrence.

Somme des $k^{2}$ .
Binôme de Newton.
Formule du crible (et tout plein d’autres trucs de dénombrements).
Formule de Taylor avec reste intégral.
Beaucoup de calculs de déterminants peuvent se faire par récurrence. Par exemple celui de Vandermonde. Pareil pour des calculs de sommes ou d’intégrales.

D’un point de vue pratique, ce sera dur de ne pas faire le tour des exos de récurrence pure et donc ces exos nécessitent parfois d’autres notions, et je pense en fait que c’est mieux comme ça.

Et ça peut être intéressant de voir des exemples où la récurrence échoue (un exemple classique est celui des crayons de couleur que voici).

On va montrer par récurrence sur $n > 0$ que tout ensemble de $n$ crayons de couleur a tous ses crayons de la même couleur. On pose donc pour tout entier $n > 0$ la propriété $P (n)$  : tout ensemble de $n$ crayons de couleurs est constitué de crayons tous de la même couleur.

$P (1)$ est trivialement vrai.

Soit $n > 0$ , on suppose $P (n)$ vraie. Considérons un ensemble de $n + 1$ crayons, on les numérote de $1$ à $n + 1$ . Par hypothèse de récurrence, les $n$ premiers crayons ont la même couleur. De même, les $n$ derniers crayons ont la même couleur. Par suite, les crayons ont tous la même couleur, d’où $P (n + 1)$ est vraie.