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