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

Début de la boite de navigation du chapitre

Le raisonnement par récurrence permet de démontrer une propriété concernant des entiers naturels

fin de la boite de navigation du chapitre

(il ne fonctionne pas sur d'autres types de nombres).

Principe de récurrence

Début d'un axiome

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

Début d’un principe

Rédaction d'une démonstration par récurrence

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}$.

Fin du principe

Exemples

Début de l'exemple

Exemple 1

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.

Solution

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.

 

Fin de l'exemple

Début de l'exemple

Exemple 2

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}}$.

Solution

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}}$.

 

Fin de l'exemple