Fiche de révision : 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}$.

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