Médaille
N°1 pour apprendre & réviser du collège au lycée.

Raisonnement par récurrence

Déjà plus de

1 million

d'inscrits !

Le raisonnement par récurrence

  • Pour démontrer par récurrence qu’une proposition PnPn est vraie pour tout entier naturel nn supérieur ou égal à un entier naturel n0n0 fixé, on procède en trois étapes.
  • Avant de commencer, on note PnP_n la proposition que l’on va démontrer.
  • Initialisation
  • On vérifie que Pn0P{n0} est vraie, c’est-à-dire que la proposition est vraie pour le premier indice n0n_0.
  • On dit qu’on a initialisé la récurrence.
  • Hérédité
  • On suppose que, pour un entier naturel quelconque kn0k \geq n0, PkPk est vraie.
    Sous cette hypothèse (dite de récurrence), on démontre que la proposition Pk+1P_{k+1} est vraie.
  • On a ainsi prouvé que l’hypothèse de récurrence « PnP_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 PnPn est vraie pour tout entier naturel nn0n \geq n0.

Exemple

  • On considère la suite (un)(un) définie par u0=1u0 = 1 et, pour tout entier naturel nn, un+1=un+1u{n+1} = \sqrt{un + 1}.

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

  • Il s’agit ici donc de démontrer que 0<unun+10 < un\leq u{n+1}, pour tout entier naturel nn.
  • Soit Pn:0<unun+1Pn : 0 < un\leq u_{n+1}.
  • Initialisation

u0=1u1=u0+1=1+1=2\begin{aligned} u0 &= 1 \ \ u1 &= \sqrt {u_0 + 1} \ &= \sqrt {1+1} \ &= \sqrt 2 \end{aligned}

On a bien : 0<1<2 0 < 1 < \sqrt 2, donc : 0<u0u10 < u0\leq u1.

  • La proposition P0P_0 est vraie.
  • Hérédité
  • Supposons la proposition PkPk vraie pour un certain entier naturel kk, c’est-à-dire : 0<ukuk+10 < uk\leq u_{k+1}
  • Montrons que la proposition Pk+1P{k+1} est vraie, c’est-à-dire que 0<uk+1uk+20 < u{k+1}\leq u_{k+2}.

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

Par récurrence, la proposition PnP_n est vraie pour tout entier naturel nn.

  • La suite (un)(u_n) est croissante et à termes strictement positifs pour tout entier naturel nn.