# Suites et récurrence/Démonstration par récurrence

Le raisonnement par récurrence permet de démontrer une propriété concernant des entiers naturels
(il ne fonctionne pas sur d'autres types de nombres).

## Principe de récurrence

Soient ${\mathcal {P}}_{n}$ une propriété dépendant de l'entier naturel $n$
    et $n_{0}$ un entier naturel.
Si :
* ${\mathcal {P}}_{n_{0}}$ est vraie ;
* pour tout entier $n\geq n_{0}$ tel que ${\mathcal {P}}_{n}$ est vraie, on a ${\mathcal {P}}_{n+1}$ vraie
Alors, pour tout entier $n\geq n_{0}$, ${\mathcal {P}}_{n}$ est vraie.

## Rédaction

On a vu que le principe de récurrence prend appui sur deux points. Il faut donc montrer ces deux points puis invoquer le principe de récurrence. Tout raisonnement par récurrence suit alors trois étapes :
* Initialisation : on vérifie que ${\mathcal {P}}_{n_{0}}$ est vraie.
* Hérédité : on suppose que ${\mathcal {P}}_{k}$ est vraie, où $k$ est un entier supérieur ou égal à $k\geq n_{0}$. Cette supposition est l'hypothèse de récurrence.
    On montre alors à partir de cette hypothèse que ${\mathcal {P}}_{k+1}$ est vraie.
* Conclusion : l'axiome de récurrence permet de conclure que ${\mathcal {P}}_{k}$ est vraie pour tout entier $n\geq n_{0}$.

## Exemples

Soit la suite $(u_{n})$ définie pour tout entier naturel par : ${\begin{cases}u_{0}=5\\u_{n+1}={\sqrt {2u_{n}-1}}\end{cases}}$.
Montrer par récurrence que $(u_{n})$ est minorée par 1.
Soit $(P_{n})$ la propriété " $u_{n}\geq 1$".
* Initialisation: $u_{0}=5\geq 1$.
* Hérédité: supposons que $u_{k}\geq 1$. On pose $k'=k+1$.
Alors (comme $2\geq 1$ ) on a : $2u_{k}\geq 2$ donc $2u_{k}-1\geq 1$ soit ${\sqrt {2u_{k}-1}}\geq 1$. Donc $u_{k'}\geq 1$ et la propriété est héréditaire.
* Conclusion: $(u_{n})$ est bien minorée par 1.
Démontrer par récurrence que pour tout entier naturel n on a :
    $\sum _{k=0}^{n}k^{2}={\frac {n(n+1)(2n+1)}{6}}$.
Tout d’abord, on énonce la propriété à démontrer. Dans notre cas, on veut montrer que pour tout entier $n\in \mathbb {N}$ (donc à partir de $n_{0}=0$) :
    $\sum _{k=0}^{n}k^{2}={\frac {n(n+1)(2n+1)}{6}}$.
On pose pour tout $n\in \mathbb {N}$ la propriété ${\mathcal {P}}_{n}$ la proposition « $\sum _{k=0}^{n}k^{2}={\frac {n(n+1)(2n+1)}{6}}$ ».
On procède ensuite à la première étape : l'initialisation.
* Initialisation
    Comme $\sum _{k=0}^{0}k^{2}=0$, la proposition ${\mathcal {P}}_{0}$ est vraie.
Ensuite, montrons l'hérédité
* Hérédité
    Soit $n\in \mathbb {N}$ tel que ${\mathcal {P}}_{n}$ soit vraie.
    Montrons que ${\mathcal {P}}_{n+1}$ est également vraie.
    Dans notre exemple, montrer que ${\mathcal {P}}_{n+1}$ est vraie consiste à montrer que $\sum _{k=0}^{n+1}k^{2}={\frac {(n+1)(n+2)(2(n+1)+1)}{6}}={\frac {(n+1)(n+2)(2n+3)}{6}}$ en sachant que ${\mathcal {P}}_{n}$ est vraie, c'est-à-dire que $\sum _{k=0}^{n}k^{2}={\frac {n(n+1)(2n+1)}{6}}$
    Allons-y :
       $\sum _{k=0}^{n+1}k^{2}=\sum _{k=0}^{n}k^{2}+(n+1)^{2}$.
    On utilise l'hypothèse de récurrence ${\mathcal {P}}_{n}$ :
       ${\begin{aligned}\sum _{k=0}^{n+1}k^{2}&={\frac {n(n+1)(2n+1)}{6}}+(n+1)^{2}\\&={\frac {n(n+1)(2n+1)}{6}}+{\frac {6(n+1)^{2}}{6}}\\&={\frac {(n+1)\left[n(2n+1)+6(n+1)\right]}{6}}\\&={\frac {(n+1)\left[2n^{2}+n+6n+6\right]}{6}}\\&={\frac {(n+1)\left[2n^{2}+7n+6\right]}{6}}\\&={\frac {(n+1)(n+2)(2n+3)}{6}}\end{aligned}}$
    Donc ${\mathcal {P}}_{n+1}$ est vraie.
* Conclusion
Pour terminer, on conclut avec l'invocation du principe de récurrence :
Le principe de récurrence permet de conclure que : $\forall n\in \mathbb {N} \quad \sum _{k=0}^{n}k^{2}={\frac {n(n+1)(2n+1)}{6}}$.
| Opérations sur les limites | Sommaire |