Raisonnement par récurrence
Définition :
Pour montrer qu'une propriété \(P(n)\) est vraie pour tout entier naturel \(n\), la démonstration par récurrence consiste à
vérifier que \(P(0)\) est vraie,
supposer que la propriété est vraie à un rang \(n\) quelconque (c'est l'hypothèse de récurrence),
démontrer qu'elle reste vraie au rang \(n+1\).
On conclut alors que la propriété \(P(n)\) est vraie quelque soit l'entier naturel \(n\).
Remarque :
La démonstration par récurrence reste valable si \(0\) est remplacé par \(1,~2,~3\) ou \(n_0\) la conclusion sera que \(P(n)\) est vraie quelque soit l'entier naturel \(n\geq n_{0}\).
Exemple :
Montrer par récurrence que pour tout entier naturel \(n\) on a :
\(0+1+2+3+...+n=\frac{n(n+1)}{2}.\)
On commence par vérifier que pour \(n=0\) on a bien que \( 0=\frac{0(0+1)}{2}\).
On suppose que pour un certain rang \(n\), on a \(0+1+2+3+...+n=\frac{n(n+1)}{2}\) ( HR[1]).
Il faut montrer que\( 0+1+2+3+...+\left( n+1\right) =\frac{(n+1)(n+2)}{2}\), en effet
\(0+1+2+3+...+\left( n+1\right) =\left[ 0+1+2+3+...+n\right] +\left(n+1\right) \)
\(=\frac{n(n+1)}{2}+\left( n+1\right)\) par l'hypothèse de récurrence.
\(=\frac{(n+1)(n+2)}{2}\).
Alors, \( 0+1+2+3+...+n=\frac{n(n+1)}{2}\) est vraie quelque soit l'entier naturel \(n\geq 0\).