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

Déjà plus de

1 million

d'inscrits !

Avant de commencer, regarde les vidéos

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 1 à nn est égale à n(n+1)2\dfrac{n(n+1)}{2}, c’est-à-dire que pour tout entier naturel nn :

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

Vérification de ce résultat pour n=2n=2 et pour n=3n=3 :

  • pour n=2n = 2 :

1+2=31+2=3 et 2(2+1)2=3\dfrac{2(2+1)}{2} = 3

  • pour n=3n = 3 :

1+2+3=61+2+3=6 et 3(3+1)2=6\dfrac{3(3+1)}{2} = 6

Même si on vérifie ce résultat jusqu’à n=100n = 100, cela ne démontre pas qu’il est vrai pour tout nn. 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 (Pn)(Pn) 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 (Pn)(P_n) la proposition que l’on va démontrer.

  • Étape 1 : Initialisation

On vérifie que (Pn0)(P{n0}) est vraie, c’est-à-dire que la proposition est vraie pour le premier indice n0n0. On dit qu’on a initialisé la récurrence.

  • Étape 2 : Hérédité

On suppose que pour un entier nn quelconque n>n0n > n0, (Pn)(Pn) est vraie, et sous cette hypothèse (dite de récurrence) on démontre que la proposition (Pn+1)(P{n+1}) est vraie. On a ainsi prouvé que l’hypothèse de récurrence « (Pn)(Pn) vraie » est héréditaire.

  • Étape 3 : Conclusion

Lorsque les deux premières étapes ont été réalisées, on conclut : par récurrence, la proposition (Pn)(Pn) est vraie pour tout entier naturel n(n>n0)n (n > n0).

Illustration

Démonstration de la formule vue en introduction à l’aide du raisonnement par récurrence :
Montrons que pour tout entier naturel nn, 1+2+3+4++n=n(n+1)21+2+3+4+…+ n = \dfrac{n(n+1)}{2}
Notons (Pn)(P_n) la proposition : 1+2+3+4++n=n(n+1)21+2+3+4+…+ n = \dfrac{n(n+1)}{2}

  • Étape 1 : Initialisation

La proposition (P1)(P_1) est vraie car 1=1(1+1)21 = \dfrac{1(1+1)}{2}

On conçoit et on admet que si l’on sait démontrer que « (Pn)(Pn) vraie » entraîne « (Pn+1)(P{n+1}) vraie », alors la proposition est vraie pour tout entier naturel n>0n > 0.

  • Étape 2 : Hérédité

Supposons donc que (Pn)(P_n) est vraie pour un entier naturel nn, c’est-à-dire que pour un entier naturel nn :

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

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

Montrons maintenant que la propriété est vraie au rang supérieur (au rang n+1n+1), c’est-à-dire que (Pn+1)(P_{n+1}) est vraie.

Autrement dit, montrons que :

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

Comme (Pn)(P_n) est vraie, alors dans la somme 1+2+3+...+n+(n+1)1+2+3+…+n+(n+1), on peut remplacer les nn premiers termes par n(n+1)2\dfrac{n(n+1)}{2}

On obtient alors :

  • 1+2+3  +  ...n+n+1=n(n+1)2+n+11 + 2 + 3\;+\;… n + n + 1 = {\dfrac{n(n+1)}{2} } + n+1

En factorisant par n+1n + 1, on obtient :

  • 1+2+3  +  ...+  n+(n+1)=(n+1)n2+(n+1)=(n+1)(n2+1)\begin{aligned}1 + 2 + 3\;+\;… +\;n + (n + 1) &= {(n+1) { \dfrac{n}{2} } } + (n+1) \&= {(n+1)}( \dfrac{n}{2} +1) \end{aligned}

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

  • 1+2+3  +  ...+  n+n+1=1 + 2 + 3\;+\;… +\;n + n + 1 = (n+1)(n+2)2\dfrac{(n+1)(n+2)}{2}

Ainsi (Pn+1)(P_{n+1}) est vraie.

  • Étape 3 : Conclusion

(Pn)(P_n) est vraie pour tout entier naturel n>0n > 0, c’est-à-dire pour tout entier naturel nn, 1+2+3  +  +  n=1+2+3\;+\;…+\;n = n(n+1)2\dfrac{n(n+1)}{2}

Exemples

Exemple 1

bannière exemple

Exemple

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

On montre par récurrence que tous les termes de la suite (un)(un) 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 de démontrer que 0<unun+10 < un\leq u{n+1}

Commençons par noter (Pn)(Pn) la proposition 0<unun+10 < un\leq u_{n+1}

  • Initialisation

u0=1u0 = 1 et u1=u0+1=(1+1)=2u1 = \sqrt {u_0+1} = \sqrt {(1+1)} = \sqrt 2

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

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

Supposons la proposition (Pn)(Pn) vraie pour un certain entier nn, c’est-à-dire : 0<unun+10 < un\leq u_{n+1}

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

Montrons que la proposition (Pn+1)(P{n+1}) est vraie (c’est-à-dire : 0<un+1un+20 < u{n+1}\leq u{n+2 }), ce qui est équivalent, en utilisant la définition de la suite (un)(u_n), à :

0<un+1un+1+10<\sqrt {un+1} \leq {\sqrt{ u{n+1} +1}}

D’après l’hypothèse de récurrence :

0<unun+10 < un\leq u{n+1}

On ajoute 1 aux inégalités :

1<un+1un+1+11 < un+1\leq u{n+1}+1

Comme la fonction racine carrée est strictement croissante sur l’intervalle [0\ ; +∞[, on obtient :

1<un+1un+1+1\sqrt1<\sqrt {un+1}\leq \sqrt { u{n+1}+1}

Soit : 0<1<un+1un+20 < 1 < u{n+1}\leq u{n+2 }

  • La propriété (Pn+1)(P_{n+1}) est donc vraie.
  • Conclusion

Par récurrence, la proposition (Pn)(Pn) est vraie pour tout entier naturel nn, donc la suite (un)(un) est croissante et à termes strictement positifs pour tout entier naturel nn.

Exemple 2

bannière exemple

Exemple

Démontrons que pour tout entier naturel nn : 4n+24^n+2 est divisible par 33.

Notons PnP_n la proposition « 4n+24^n+2 est divisible par 33 ».

  • Initialisation

Pour n=0n = 0, on a 40+2=1+2=34^0+2=1+2=3 et 33 est bien divisible par 3.3.

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

Supposons la proposition PnP_n vraie pour un entier nn.

  • Conclusion

On a alors 4n+24^n+2 est divisible par 33, c’est-à-dire qu’il existe un nombre bb tel que 4n+2=3×b4^n+2=3\times b

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

Astuce

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

Montrons maintenant que la proposition PnP_n est vraie au rang n+1n+1, c’est à dire que 4n+1+24^{n+1}+2 est aussi divisible par 33.

  • On cherche à montrer qu’il existe un entier kk tel que 4n+1+2=3×k4^{n+1}+2 = 3 \times k

On a : 4n+2=3×b4^n+2=3\times b

  • On soustrait 22 à l’égalité :

4n=3×b24^n=3\times b -2

  • De plus :

4n+1+2=4n×4+24^{n+1}+2 = 4^n \times 4 +2

  • On remplace 4n4^n par (3 × b - 2) :

4n+1+2=(3×b2)×4+24^{n+1}+2 =( 3\times b-2) \times 4 +2

  • On développe :

4n+1+2=(3×b2)×4+2=12b8+2=12b6\begin{aligned}4^{n+1}+2 &=( 3\times b-2) \times 4 +2 \ &= 12b-8+2 \ &=12b-6\end{aligned}

  • On factorise par 33 :

4n+1+2=3×(4b2)4^{n+1}+2 = 3 \times (4b -2)

Comme le nombre 4b24b - 2 est un entier alors on a bien 4n+1+2=3×k4^{n+1}+2=3\times k en posant k=4b2k = 4b - 2

  • Donc la proposition Pn+1P_{n+1} est vraie.
  • Conclusion

Par récurrence, pour tout entier naturel nn, PnP_n est vraie, donc pour tout entier naturel nn, 4n+24^n+2 est divisible par 33.

Exemple 3

bannière exemple

Exemple

Soit (un)(un) la suite définie par u0=2u0= 2 et pour tout entier naturel n>0n>0 :

un+1=un1+unu{n+1} ={ \dfrac{un}{1+u_n}}

Démontrons que pour tout n∈ \mathbb N, un=22n+1u_n={\dfrac{2}{2n+1}}

Notons PnPn la proposition « un=22n+1un={\dfrac{2}{2n+1}}  »

  • Initialisation

Pour n=0n = 0, u0=2u_0 = 2 et 22×0+1=2{\dfrac{2}{2 \times 0 +1} } = 2

Donc la proposition P0P_0 est vraie.

  • Hérédité

Supposons la proposition PnPn vraie pour un entier nn, c’est-à-dire que pour un entier nn, un=22n+1u_n={\dfrac{2}{2n+1}}

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

On montre maintenant que la proposition est vraie au rang n+1n + 1, c’est-à-dire que un+1=22(n+1)+1u_{n+1}={\dfrac{2}{2(n+1)+1}}

Par définition de la suite unun, on a un+1=un1+unu{n+1} ={ \dfrac{un}{1+un}} et d’après l’hypothèse de récurrence cela donne : un+1=22n+11+22n+1u_{n+1}= { \dfrac{{\dfrac{2}{2n+1}}}{1+{\dfrac{2}{2n+1}}} }

En réduisant au même dénominateur et en simplifiant par 2n+12n + 1, on obtient :

un+1=22n+1+2u_{n+1}={\dfrac{2}{2n+1+2}}

ce qui est égal à un+1=22(n+1)+1u_{n+1}={\dfrac{2}{2(n+1)+1}}

  • Donc la proposition Pn+1P_{n+1} est vraie.
  • Conclusion

Par récurrence, pour tout entier naturel nn, PnP_n est vraie, c’est-à-dire que pour tout entier naturel nn :

un=22n+1u_n={\dfrac{2}{2n+1}}