• 6ème

  • 5ème

  • 4ème

  • 3ème

  • Seconde

  • 1re S

  • 1re ES

  • 1re L

  • 1re STMG

  • Terminale S

  • Terminale ES

  • Terminale L

  • Terminale STMG

Consulter notre FAQ
croix de fermeture
Classe
Connexion
Inscription
  1. Terminale S
  2. Mathématiques
  3. Programme
  4. Le raisonnement par récurrence

Vidéo

Fiche de cours

Fiche de révision

Quiz

Exercices

NOUVEAU

Le raisonnement par récurrence

Avant de commencer, regarde les vidéos

Épisode 1

1. Principe et illustration

Épisode 2

2. Exemples

Introduction :

En mathématiques, un certain nombre de propriétés dépendent d’un entier naturel nnn.

Par exemple, la somme des entiers naturels de 1 à nnn est égale à n(n+1)2\dfrac{n(n+1)}{2}2n(n+1)​, c’est-à-dire que pour tout entier naturel nnn :

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

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

  • pour n=2n = 2n=2 :

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

  • pour n=3n = 3n=3 :

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

Même si on vérifie ce résultat jusqu’à n=100n = 100n=100, cela ne démontre pas qu’il est vrai pour tout nnn. 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)(P_n)(Pn​) est vraie pour tout entier naturel nnn supérieur ou égal à un entier naturel n0n_0n0​ fixé, on procède en trois étapes.

Avant de commencer, on note (Pn)(P_n)(Pn​) la proposition que l’on va démontrer.

  • Étape 1 : Initialisation

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

  • Étape 2 : Hérédité

On suppose que pour un entier nnn quelconque n>n0n > n_0n>n0​, (Pn)(P_n)(Pn​) est vraie, et sous cette hypothèse (dite de récurrence) on démontre que la proposition (Pn+1)(P_{n+1})(Pn+1​) est vraie. On a ainsi prouvé que l’hypothèse de récurrence « (Pn)(P_n)(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)(P_n)(Pn​) est vraie pour tout entier naturel n(n>n0)n (n > n_0)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 nnn, 1+2+3+4+…+n=n(n+1)21+2+3+4+…+ n = \dfrac{n(n+1)}{2}1+2+3+4+…+n=2n(n+1)​
Notons (Pn)(P_n)(Pn​) la proposition : 1+2+3+4+…+n=n(n+1)21+2+3+4+…+ n = \dfrac{n(n+1)}{2}1+2+3+4+…+n=2n(n+1)​

  • Étape 1 : Initialisation

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

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

  • Étape 2 : Hérédité

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

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

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

Montrons maintenant que la propriété est vraie au rang supérieur (au rang n+1n+1n+1), c’est-à-dire que (Pn+1)(P_{n+1})(Pn+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}1+2+3+...+n+(n+1)=2(n+1)(n+2)​

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

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 1+2+3+...n+n+1=2n(n+1)​+n+1

En factorisant par n+1n + 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}1+2+3+...+n+(n+1)​=(n+1)2n​+(n+1)=(n+1)(2n​+1)​

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 = 1+2+3+...+n+n+1= (n+1)(n+2)2\dfrac{(n+1)(n+2)}{2}2(n+1)(n+2)​

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

  • Étape 3 : Conclusion

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

Exemples

Exemple 1

bannière exemple

Exemple

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

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

bannière rappel

Rappel

Une suite (un)(u_n)(un​) est croissante si pour tout entier naturel nnn, un≤un+1u_n\leq u_{n+1}un​≤un+1​

Il s’agit de démontrer que 0<un≤un+10 < u_n\leq u_{n+1}0<un​≤un+1​

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

  • Initialisation

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

On a bien 0<1<2 0 <1 < \sqrt 2 0<1<2​ donc 0<u0≤u10 < u_0\leq u_10<u0​≤u1​

  • Donc la proposition P0P_0P0​ est vraie.
  • Hérédité

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

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

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

0<un+1≤un+1+10<\sqrt {u_n+1} \leq {\sqrt{ u_{n+1} +1}} 0<un​+1​≤un+1​+1​

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

0<un≤un+10 < u_n\leq u_{n+1}0<un​≤un+1​

On ajoute 1 aux inégalités :

1<un+1≤un+1+11 < u_n+1\leq u_{n+1}+11<un​+1≤un+1​+1

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

1<un+1≤un+1+1\sqrt1<\sqrt {u_n+1}\leq \sqrt { u_{n+1}+1}1​<un​+1​≤un+1​+1​

Soit : 0<1<un+1≤un+20 < 1 < u_{n+1}\leq u_{n+2 }0<1<un+1​≤un+2​

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

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

Exemple 2

bannière exemple

Exemple

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

Notons PnP_nPn​ la proposition « 4n+24^n+24n+2 est divisible par 333 ».

  • Initialisation

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

  • Donc la proposition P0P_0P0​ est vraie.
  • Hérédité

Supposons la proposition PnP_nPn​ vraie pour un entier nnn.

  • Conclusion

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

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

Astuce

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

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

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

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

  • On soustrait 222 à l’égalité :

4n=3×b−24^n=3\times b -24n=3×b−2

  • De plus :

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

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

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

  • On développe :

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

  • On factorise par 333 :

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

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

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

Par récurrence, pour tout entier naturel nnn, PnP_nPn​ est vraie, donc pour tout entier naturel nnn, 4n+24^n+24n+2 est divisible par 333.

Exemple 3

bannière exemple

Exemple

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

un+1=un1+unu_{n+1} ={ \dfrac{u_n}{1+u_n}}un+1​=1+un​un​​

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

Notons PnP_nPn​ la proposition « un=22n+1u_n={\dfrac{2}{2n+1}}un​=2n+12​  »

  • Initialisation

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

Donc la proposition P0P_0P0​ est vraie.

  • Hérédité

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

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

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

Par définition de la suite unu_nun​, on a un+1=un1+unu_{n+1} ={ \dfrac{u_n}{1+u_n}}un+1​=1+un​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}}} } un+1​=1+2n+12​2n+12​​

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

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

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

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

Par récurrence, pour tout entier naturel nnn, PnP_nPn​ est vraie, c’est-à-dire que pour tout entier naturel nnn :

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

Télécharger en PDF

Cette fiche de cours fait appel aux contenus suivants

Fonction racine carrée

Définition

Icone MatièreMathématiques