Licence CC BY

Le raisonnement par récurrence

Une méthode de démonstration mathématique redoutablement efficace

Publié :
Auteurs :
Catégorie :
Temps de lecture estimé : 41 minutes

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 à 00) inférieurs à 100100, 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 : 50505050. 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==50+51=101.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++100=(1+100)+(2+99)++(50+51)=1002101=5050.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 00 à nn, où nn est un entier naturel1. 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ématiques2 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.


  1. Si n=0n = 0, la somme est simplement nulle.

  2. Elle était déjà parfaitement maîtrisée au XVIIe siècle, par Pascal, Fermat et Bernoulli notamment.

Le principe de récurrence

  1. Revenons à notre somme
  2. Le raisonnement par récurrence
  3. Plus généralement : des suites de propositions


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.

4 commentaires

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.

@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).

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

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

  • Somme des k2k^2k2.
  • 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>0n > 0n>0 que tout ensemble de nnn crayons de couleur a tous ses crayons de la même couleur. On pose donc pour tout entier n>0n > 0n>0 la propriété P(n)P(n)P(n) : tout ensemble de nnn crayons de couleurs est constitué de crayons tous de la même couleur.

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

Ceci est bien évidemment faux, reste à trouver l’erreur dans le raisonnement.

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
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte