Raisonnement par récurrence

Raisonnement par récurrence

Raisonnement par récurrence

 

Principe

 

bf8e2989fba472800b9033b22798f33f3dbe1abd.png


Considérons une chaîne de dominos, faire tomber un domino entraîne son plus proche voisin dans sa chute et ainsi de suite.

Le raisonnement par récurrence utilise ce principe. Il existe des conditions pour que l’ensemble des dominos tombe.

Il faut, dans un premier temps, pousser le premier domino et dans un second temps, il faut être certain que la chute de n’importe quel domino entraîne le suivant.

 

Mathématiquement, $P_n$ désigne une proposition qui dépend d’un entier naturel $n$ et on souhaite démontrer que $P_n$ est vraie.

Le raisonnement par récurrence se divise en deux parties.

 

I. Initialisation

 

La première est l’initialisation : il faut vérifier que $P_0$ ou $P_1$ est vraie c’est-à-dire que la propriété est vraie pour $n=0$ ou $n=1$ (et par analogie, il faut pousser le premier domino).

 

II. Hérédité

 

La deuxième est l’hérédité : on suppose que $P_n$ est vraie pour un certain $n$ et on démontre que $P_{n + 1}$ est vraie (par analogie, on considère que le $n^\text{ème}$ domino tombe et on cherche à savoir si le domino suivant, le $(n + 1)^\text{ème}$, tombe également).

 

En ayant prouvé ces deux parties, cela prouve l’ensemble de la propriété pour tout entier $n$ (tous les dominos tombent).

Raisonnement par récurrence - Exercice

Exercice

 

Démontrer que  pour tout $n\geq 1$ :

\(1 + 2+ 3 + … + n = \dfrac{n(n+1)}{2}\).

  • Étape 1 : Initialisation. On vérifie que la proposition est vraie au rang 1.
  • Étape 2 : Hérédité. On suppose que la proposition est vraie au rang n et on vérifie qu’elle l’est au rang n + 1.

Tu veux réviser 2x plus vite ?

Découvre les offres des Bons Profs avec :