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.

1 commentaire

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.github.ioAnagrams

+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