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 !

Avant de commencer, regarde la vidéo

Introduction :

En mathématiques, un certain nombre de propriétés dépendent d’un entier naturel nn.
Par exemple, la somme des entiers naturels de 11 à nn est égale à n(n+1)2\frac{n(n+1)}{2}, c’est-à-dire que pour tout entier naturel n>0n> 0 :

1+2+3++n=n(n+1)21+2+3+…+n =\dfrac{n(n+1)}{2}

Nous pouvons vérifier ce résultat pour n=2n=2 et pour n=3n=3 :

Pour n=2n = 2 :

1+2=32(2+1)2=3\begin{aligned} 1+2&=3 \ \dfrac{2(2+1)}{2} &= 3 \end{aligned}

Pour n=3n = 3 :

1+2+3=63(3+1)2=6\begin{aligned} 1+2+3&=6 \ \dfrac{3(3+1)}{2} &= 6 \end{aligned}

Même si ce résultat est vrai jusqu’à n=100n = 100, cela ne démontre pas pour autant qu’il est vrai pour tout nNn\in \mathbb N^*.
Pour effectuer cette démonstration, on dispose d’un outil particulier : le raisonnement par récurrence.

Le raisonnement par récurrence

Principe

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.

En effet :

  • on a montré que Pn0P{n0} est vraie ;
  • on a démontré l’hérédité : si PkPk est vraie, alors Pk+1P{k+1} est vraie ;
  • donc, avec n=n0n=n0, Pn0+1P{n_0+1} est vraie ;
  • par hérédité, P(n0+1)+1=Pn0+2P{(n0+1)+1}=P{n0+2} est vraie ;
  • toujours par hérédité, P(n0+2)+1=Pn0+3P{(n0+2)+1}=P{n0+3} est aussi vraie ;
  • et ainsi de suite…
  • C’est ce que l’on appelle un raisonnement par récurrence.

Illustration

Démontrons maintenant la formule vue en introduction à l’aide du raisonnement par récurrence et montrons que, pour tout entier naturel nNn \in \mathbb N^*, 1++n=n(n+1)21+…+ n = \frac{n(n+1)}{2}.

  • Notons PnP_n la proposition : 1++n=n(n+1)21+…+ n = \dfrac{n(n+1)}{2}.
  • Initialisation

La proposition P1P_1 est vraie, car 1=1(1+1)21 = \dfrac{1(1+1)}{2} .

On conçoit donc que, si l’on sait démontrer que, pour n1n \geq 1, « PnPn vraie » entraîne « Pn+1P{n+1} vraie », alors la proposition est vraie pour tout entier naturel n1n \geq 1.

  • Hérédité

Supposons donc que PkP_k est vraie pour un entier naturel k1k \geq 1, c’est-à-dire que, pour un entier naturel k1k \geq 1 :

1+2++(k1)+k=k(k+1)21+2+… + (k-1) + k =\dfrac{k(k+1)}{2}

  • C’est l’hypothèse de récurrence.

Montrons maintenant que la propriété est vraie au rang supérieur (k+1k+1), c’est-à-dire que Pk+1P_{k+1} est vraie.
Autrement dit, montrons que :

1+2++k+(k+1)=(k+1)((k+1)+1)21+2+…+k+(k+1) =\dfrac{(k+1)\big((k+1)+1\big)}{2}

Comme PkP_k est vraie, dans la somme 1+2++k+(k+1)1+2+…+k+(k+1), on peut remplacer les kk premiers termes par k(k+1)2\frac{k(k+1)}{2}.

  • On obtient alors :

1+2++k+(k+1)=(1+2++k)k(k+1)2+(k+1)=k(k+1)2+(k+1)\begin{aligned} 1+2+…+k+(k+1)&=\overbrace{(1 + 2 + … + k)}^{ \frac{k(k+1)}{2}} + (k + 1) \ &=\dfrac{k(k+1)}{2} + (k+1) \end{aligned}

  • En factorisant par (k+1)(k + 1), on obtient :

1+2++k+(k+1)=(k+1)k2+(k+1)=(k+1)(k2+1)\begin{aligned} 1 + 2 + … + k + (k + 1)&= (k+1) \dfrac{k}{2} + (k+1) \ &= {(k+1)}\Big( \dfrac{k}{2} +1\Big) \end{aligned}

  • En réduisant le deuxième facteur au même dénominateur 22, on a :

1+2++k+(k+1)=(k+1)k+22=(k+1)((k+1)+1)2\begin{aligned} 1 + 2 + … + k + (k + 1)&=(k+1)\dfrac{k+2}{2} \ &=\dfrac{(k+1)\big((k+1)+1\big)}{2} \end{aligned}

  • Ainsi, Pk+1P_{k+1} est vraie.
  • Conclusion

PnP_n est vraie pour tout entier naturel n1n \geq 1.

  • C’est-à-dire que, pour tout entier naturel n1n \geq 1 :

1++n=n(n+1)21 + … + n =\dfrac{n(n+1)}{2}

Exemples

La meilleure façon de se familiariser avec le raisonnement par récurrence, c’est de le travailler. Nous donnons donc ici quatre exemples d’un tel raisonnement.

  • N’hésitez pas à mener vous-même le raisonnement à partir de la formule à démontrer, avant de regarder le déroulé donné.

Exemple 1

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.

bannière rappel

Rappel

Une suite (un)(un) est croissante si, pour tout entier naturel nn, unun+1un\leq u_{n+1}.

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

  • Commençons par noter PnPn la proposition : 0<unun+10 < 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 PkP_k vraie pour un certain entier naturel kk, c’est-à-dire :

0<ukuk+10 < uk\leq u{k+1}

  • C’est l’hypothèse de récurrence.

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}.
En utilisant la définition de la suite (un)(u
n), c’est équivalent à :

0<uk+1uk+1+10<\sqrt {uk +1} \leq \sqrt{ u{k+1} +1}

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.

Exemple 2

Démontrons que, pour tout entier naturel nn, (4n+2)(4^n+2) est divisible par 33.

  • Notons PnP_n la proposition « (4n+2)(4^n+2) est divisible par 33 ».
  • Initialisation

Pour n=0n = 0, on a :

40+2=1+2=3\begin{aligned} 4^0+2&=1+2 \ &=3 \end{aligned}

33 est bien divisible par 33.

  • La proposition P0P_0 est vraie.
  • Hérédité

Supposons la proposition PkP_k vraie pour un entier naturel kk.

bannière astuce

Astuce

Pour montrer qu’un entier xx est divisible par un entier aa, il faut montrer qu’il existe un entier bb tel que x=a×bx = a \times b.

(4k+2)(4^k+2) est divisible par 33, c’est-à-dire qu’il existe un entier relatif bb tel que 4k+2=3×b4^k+2=3\times b.

  • C’est l’hypothèse de récurrence.

Montrons maintenant que la proposition Pk+1P_{k+1} est vraie, c’est à dire que (4k+1+2)(4^{k+1}+2) est aussi divisible par 33.

On cherche à montrer qu’il existe un entier relatif cc tel que 4k+1+2=3×c4^{k+1}+2 = 3 \times c.

Hypothèse de récurrence : 4k+2=3×b4^k+2=3\times b
On soustrait 22 à l’égalité : 4k=3×b24^k=3\times b -2
De plus : 4k+1+2=4k×4+24^{k+1}+2 = 4^k \times 4 +2
On remplace 4k4^k par (3×b2)(3 \times b - 2) : 4k+1+2=(3×b2)×4+24^{k+1}+2 =( 3\times b-2) \times 4 +2
On développe : 4k+1+2=12b8+2=12b6\begin{aligned} 4^{k+1}+2 &= 12b-8+2 \ &=12b-6 \end{aligned}
On factorise par 33 : 4k+1+2=3×(4b2)4^{k+1}+2 = 3 \times (4b -2)
bb étant un entier relatif, 4b24b-2 est donc aussi un entier relatif. Posons ainsi un entier relatif cc tel que 4b2=c4b-2=c. On obtient : 4k+1+2=3×c4^{k+1}+2 = 3 \times c
  • Donc la proposition Pk+1P_{k+1} est vraie.
  • Conclusion

Pour tout entier naturel nn, PnP_n est vraie.

  • Pour tout entier naturel nn, 4n+24^n+2 est divisible par 33.

Exemple 3

Soit (un)(un) la suite définie par u0=2u0= 2 et, pour tout entier naturel nn, un+1=un1+unu{n+1} =\frac{un}{1+u_n}.

Démontrons que, pour tout nNn\in\mathbb N, un=22n+1u_n=\frac{2}{2n+1}.

  • Notons PnPn la proposition « un=22n+1un=\frac{2}{2n+1} ».
  • Initialisation

Pour n=0n = 0 :

u0=222×0+1=2\begin{aligned} u_0 &= 2 \ \dfrac{2}{2 \times 0 +1} &= 2 \end{aligned}

  • La proposition P0P_0 est vraie.
  • Hérédité

Supposons la proposition PkP_k vraie pour un entier naturel kk, c’est-à-dire que, pour un entier naturel kk :

uk=22k+1u_k=\frac{2}{2k+1}

  • C’est l’hypothèse de récurrence.

Montrons maintenant que la proposition est vraie au rang (k+1)(k + 1), c’est-à-dire :

uk+1=22(k+1)+1u_{k+1}=\frac{2}{2(k+1)+1}

Hypothèse de récurrence : uk=22k+1uk= \dfrac{2}{2k+1}
Par définition de la suite : uk+1=uk1+uku{k+1} =\dfrac{uk}{1+uk}
On remplace ukuk par 22k+1\dfrac{2}{2k+1} : uk+1=22k+11+22k+1u{k+1}= \dfrac{\frac{2}{2k+1}}{1+\frac{2}{2k+1}}
On réduit au même dénominateur le dénominateur du deuxième terme : uk+1=22k+12k+1+22k+1=22k+1×2k+12k+1+2\begin{aligned} u{k+1}&= \dfrac{\frac{2}{2k+1}}{\frac{2k+1+2}{2k+1}} \ &=\dfrac 2{2k+1}\times \dfrac {2k+1}{2k+1+2} \end{aligned}
On simplifie par (2k+1)(2k+1) : uk+1=22k+2+1u{k+1}= \dfrac{2}{2k+2+1}
On factorise (2k+2)(2k+2) par 22 : uk+1=22(k+1)+1u_{k+1}= \dfrac{2}{2(k+1)+1}
  • Donc la proposition Pk+1P_{k+1} est vraie.
  • Conclusion

Pour tout entier naturel nn, PnP_n est vraie.

  • Pour tout entier naturel nn, un=22n+1u_n={\dfrac{2}{2n+1}}.

Exemple 4 : inégalité de Bernoulli

L’inégalité de Bernoulli dit que, pour tout réel xx strictement positif et nn entier naturel, (1+x)n1+nx(1+x)^n \geq 1 + nx.

Nous utiliserons cette inégalité dans le cours suivant, sur les suites. Nous allons donc la démontrer ici, par récurrence.

Soit xx un réel strictement positif.

  • Notons PnP_n la proposition « (1+x)n1+nx(1+x)^n \geq 1 + nx ».
  • Initialisation

Pour n=0n = 0 :

(1+x)0=11+0×x\begin{aligned} (1+x)^0 &= 1 \ & \geq 1 + 0\times x \end{aligned}

  • Donc la proposition P0P_0 est vraie.
  • Hérédité

Supposons la proposition PkP_k vraie pour un entier naturel kk, c’est-à-dire, que pour un entier naturel kk :

(1+x)k1+kx(1+x)^k \geq 1 + kx

  • C’est l’hypothèse de récurrence.

Montrons maintenant que la proposition est vraie au rang (k+1)(k + 1), c’est-à-dire :

(1+x)k+11+(k+1)x(1+x)^{k+1} \geq 1 + (k+1)x

On a : (1+x)k+1=(1+x)k×(1+x)(1+x)^{k+1} = (1+x)^k \times (1+x)
Hypothèse de récurrence : (1+x)k1+kx{(1+x)}^k \geq 1 + kx
D’où, en multipliant par (1+x)(1+x) (x>0x>0, donc x+1>0x+1>0, et cela ne change pas le sens des inégalités) : (1+x)k+1(1+kx)(1+x)(1+x)^{k+1} \geq (1 + kx)(1 + x)
On développe : (1+x)k+11+x+kx+kx2(1+x)^{k+1} \geq 1 + x + kx + k x^2
On factorise (x+kx)(x+kx) par xx : (1+x)k+11+x(k+1)+kx2(1+x)^{k+1} \geq 1 + x(k+1) + k x^2
kk étant un entier positif, kx20kx^2\geq0 : 1+x(k+1)+kx21+(k+1)x 1 + x(k+1) + k x^2 \geq 1 + (k+1)x
D’où : (1+x)k+11+(k+1)x{(1+x)}^{k+1} \geq 1 + (k+1)x
  • La proposition Pk+1P_{k+1} est vraie.
  • Conclusion

Pour tout entier naturel nn, PnP_n est vraie.

  • Pour tout entier naturel nn et tout réel xx strictement positif, (1+x)k1+kx(1+x)^k \geq 1 + kx.

Conclusion :

Dans ce cours, nous avons vu ce principe puissant qu’est le raisonnement par récurrence : il permet de démontrer assez rapidement une propriété sur l’ensemble des entiers naturels, ou une partie de cet ensemble.
Ainsi, notamment en travaillant sur les suites, nous ferons souvent appel à ce type de raisonnement.