Raisonnement par récurrence

Pour montrer que \(P(n): \forall n \in \mathbb{N}, n \geq n_{0}, P_{n}(x)\) est vraie on suit les étapes suivantes :

  • On montre que \(P\left(n_{0}\right)\) est vraie, (valeur initiale).

  • On suppose que \(P(n)\) est vraie à l'ordre \(n\)

  • ( On montre que \(P(n+1)\) est vraie à l'ordre \(n+1\)

Alors \(P\) est vrai pour tous \(n \geq n_{0}\).

Exemple

Montrer \(\forall n \in \mathbb{N}^{*}: 1+2+\ldots+n=\frac{n(n+1)}{2}\)

  • Pour \(n=1, P(1)\) est vaie \(1=\frac{1(2)}{2}\).

  • On suppose que \(1+2+\ldots+n=\frac{n(n+1)}{2}\) est vraie.

  • On montre que \(1+2+\ldots+n+1=\frac{(n+1)(n+2)}{2}\) est vraie,

\(1+2+\ldots+n+1=1+2+\ldots+n+(n+1)=\frac{n(n+1)}{2}+(n+1)=\frac{(n+1)(n+2)}{2}\)

ainsi \(P\) est vraie à l'ordre \(n+1\) alors \(\forall n \in \mathbb{N}^{*}: 1+2+\ldots+n=\frac{n(n+1)}{2}\) est vraie.