Raisonnement par récurrence

Le raisonnement par récurrence

  • Pour démontrer par récurrence qu’une proposition $P_n$ est vraie pour tout entier naturel $n$ supérieur ou égal à un entier naturel $n_0$ fixé, on procède en trois étapes.
  • Avant de commencer, on note $P_n$ la proposition que l’on va démontrer.
  • Initialisation
  • On vérifie que $P_{n_0}$ est vraie, c’est-à-dire que la proposition est vraie pour le premier indice $n_0$.
  • On dit qu’on a initialisé la récurrence.
  • Hérédité
  • On suppose que, pour un entier naturel quelconque $k \geq n_0$, $P_k$ est vraie.
    Sous cette hypothèse (dite de récurrence), on démontre que la proposition $P_{k+1}$ est vraie.
  • On a ainsi prouvé que l’hypothèse de récurrence « $P_n$ vraie » est héréditaire.
  • Conclusion
  • Lorsque les deux premières étapes ont été réalisées, on peut conclure.
  • Par récurrence, la proposition $P_n$ est vraie pour tout entier naturel $n \geq n_0$.

Exemple

  • On considère la suite $(u_n)$ définie par $u_0 = 1$ et, pour tout entier naturel $n$, $u_{n+1} = \sqrt{u_n + 1}$.

Montrons par récurrence que tous les termes de la suite $(u_n)$ sont strictement positifs et que la suite est croissante.

  • Il s’agit ici donc de démontrer que $0 < u_n\leq u_{n+1}$, pour tout entier naturel $n$.
  • Soit $P_n : 0 < u_n\leq u_{n+1}$.
  • Initialisation

$\begin{aligned} u_0 &= 1 \\ \\ u_1 &= \sqrt {u_0 + 1} \\ &= \sqrt {1+1} \\ &= \sqrt 2 \end{aligned}$

On a bien : $ 0 < 1 < \sqrt 2$, donc : $0 < u_0\leq u_1$.

  • La proposition $P_0$ est vraie.
  • Hérédité
  • Supposons la proposition $P_k$ vraie pour un certain entier naturel $k$, c’est-à-dire : $$0 < u_k\leq u_{k+1}$$
  • Montrons que la proposition $P_{k+1}$ est vraie, c’est-à-dire que $0 < u_{k+1}\leq u_{k+2}$.

Hypothèse de récurrence : $0 < u_k\leq u_{k+1}$
On ajoute $1$ aux inégalités : $1 < u_k+1\leq u_{k+1}+1$
Comme la fonction racine carrée est strictement croissante sur l’intervalle $[0\ ; +\,\infty[$, elle ne change pas le sens des inégalités, et on obtient : $\sqrt1<\sqrt {u_k+1}\leq \sqrt { u_{k+1}+1}$
Soit : $0 < 1 < u_{k+1}\leq u_{k+2 }$
  • La propriété $P_{k+1}$ est donc vraie.
  • Conclusion

Par récurrence, la proposition $P_n$ est vraie pour tout entier naturel $n$.

  • La suite $(u_n)$ est croissante et à termes strictement positifs pour tout entier naturel $n$.
Ce contenu est réservé à nos inscrits. Il reste 50% à lire.
Inscrivez-vous gratuitement pour lire la suite
Inscrivez-vous pour lire la suite et accéder à nos vidéos, quiz, exercices, méthodes… Tout ce qu’il faut pour augmenter sa moyenne. 😉