Le raisonnement par récurrence

Une démonstration par récurrence repose sur le principe de transmission de proche en proche (ou hérédité).

En effet, une fois que le premier élément transmet à l'autre, c'est par la suite une réaction en chaîne.

En revanche, cela présuppose qu'il y a eu un premier mouvement à l'initiative du processus.

C'est pourquoi lorsque l'on démontre par récurrence, on démontre d'abord l'existence d'un terme initial.

Étapes :

En premier lieu, on met en évidence la proposition que l'on souhaite démontrer : par exemple (\( P_n\)). Ensuite, on suit les étapes suivantes :

1. Vérification que c'est vrai pour le premier terme : \( n = n_0\)

2. Démonstration de la transmission de proche en proche :

   • supposition de la proposition vraie à un certain rang \(n\);

   • démonstration qu'avec cette hypothèse prise pour vraie, il existe une transmission au rang suivant \((n+1)\).

3. Conclusion : la proposition de départ est bien vraie pour tout rang \(n \geqslant n_0\).

Voici un exemple qui illustre ce principe et le détail du processus.

La somme des premiers entier naturels : \(\sum k\)

Démontrons la proposition suivante \((P_n)\) par une récurrence :

1. Vérification de la proposition pour le premier terme : \(P_0\)

   Calculons les deux membres séparément, et vérifions s'il sont égaux :

   $$ Pour \ n = 0 \ : $$
   $$ \sum_{k = 0}^n k = 0 $$

   $$ \frac{n \times (n+1)}{2} = \frac{0 \times (0+1)}{2} = 0 $$

   La proposition \((P_n)\) est vraie au rang \((n = 0)\) .

2. Démonstration de la transmission de proche en proche : \(P_n \Longrightarrow P_{n+1} \)

   Supposons que la proposition suivante est vraie à un certain rang \(n\).

   $$ \forall n \in \hspace{0.03em} \mathbb{N}, \ \sum_{k = 0}^n k = \frac{n(n+1)}{2} \qquad(P_n) $$

   Et démontrons que si cette proposition est vraie, la proposition du rang suivant \((P_{n+1}) \) l'est aussi :

   $$ \forall n \in \hspace{0.03em} \mathbb{N}, \ \sum_{k = 0}^{n+1} k = \frac{(n+1)(n+2)}{2} \qquad(P_{n+1}) $$
   
   

   Entre les deux sommes, on a seulement ajouté \((n+1\)) :

   $$ \sum_{k = 0}^{n+1} k = \sum_{k = 0}^n k + (n+1) \qquad (1) $$

   Injectons la valeur de cette somme, supposée vraie auparavant, prise dans l'expression de \((P_n)\) :

   $$ \sum_{k = 0}^{n+1} k = \frac{n(n+1)}{2} + (n+1) $$

   On met au même dénominateur :

   $$ \sum_{k = 0}^{n+1} k = \frac{n(n+1)}{2} + (n+1) \textcolor{#6187B2}{ \times \frac{2}{2}} $$
   $$ \sum_{k = 0}^{n+1} k = \frac{n(n+1) + 2(n+1)}{2} $$

   Puis on factorise :

   $$ \sum_{k = 0}^{n+1} k = \frac{(n+1)(n+2)}{2} \qquad(P_{n+1}) $$

   On a bien montré que si \((P_n)\) est vraie, la proposition au rang suivant \((P_{n+1})\) l'est aussi. On a donc donc bien démontré l'hérédité .

3. Conclusion

   On a montré que la proposition \((P_n)\) était hériditaire pour tout \(n \), et qu'elle est aussi vraie pour son terme de rang initial \((n_0 = 0)\).

   
   

   Alors, on a démontré par récurrence que la proposition \((P_n)\) est bien vraie pour tout \(n \geqslant 0 \).