Index

Imprimer

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