II. MISE EN OEUVRE

Soit $n$ un entier naturel, et soit ${\mathcal{P}}_n$ une propriété dépendant de $n$.

Pour démontrer que ${\mathcal{P}}_n$ est vraie pour tout $n$ de $\mathbb{N}$, on peut procéder de la façon suivante :

• Initialisation : On établit la propriété au premier rang (ex. pour $n=0$).

• Hérédite : On fixe un entier $n$ tel que la propriété ${\mathcal{P}}_n$ soit vraie. On montre alors que ${\mathcal{P}}_{n+1}$ est également vraie.

Ces deux points étant établis, on peut conclure que la propriété ${\mathcal{P}}_n$ est vraie pour tout $n$.

 

— EXEMPLE 1 —

Somme des $n$ premiers entiers.

Montrer par récurrence que :

$$\mathrm{\forall }n\in \mathbb{N},0+1+2+\cdots +(n-1)+n=\frac{n(n+1)}{2}$$

Correction :

Pour $n$ dans $\mathbb{N}$, on note ${\mathcal{P}}_n$ la propriété :

$$0+1+2+\cdots +(n-1)+n=\frac{n(n+1)}{2}$$

Initialisation :

La vérification de ${\mathcal{P}}_0$ est immédiate. En effet,

$$0=\frac{0(0+1)}{2}=0$$

Hérédité :

Fixons $n$ dans $\mathbb{N}$ tel que ${\mathcal{P}}_n$ soit vraie. On a donc :

$$0+1+2+\cdots +(n-1)+n=\frac{n(n+1)}{2}$$

Puisque,

$$0+1+2+\cdots +(n-1)+n+(n+1)=(0+1+2+\cdots +(n-1)+n)+(n+1)$$

Alors, grâce à ${\mathcal{P}}_n$ on a,

$$\begin{array}{rl}0+1+2+\cdots +(n-1)+n+(n+1)& =\frac{n(n+1)}{2}+(n+1)\\ & =\frac{n(n+1)+2(n+1)}{2}\\ & =\frac{(n+1)(n+2)}{2}\end{array}$$

C’est exactement ${\mathcal{P}}_{n+1}$. ${\mathcal{P}}_{n+1}$ est donc vraie.

On peut donc conclure que la propriété ${\mathcal{P}}_n$ est vraie pour tout $n$.

C’est à dire que pour tout $n\in \mathbb{N}$, on a : ${\displaystyle 0+1+2+\cdots +(n-1)+n=\frac{n(n+1)}{2}}$.

 

— EXEMPLE 2 —

Somme des carrés des $n$ premiers entiers :

Montrer par récurrence que :

$$\mathrm{\forall }n\in {\mathbb{N}}^{\ast },1^2+2^2+3^2+\cdots +(n-1{)}^2+n^2=\frac{n(n+1)(2n+1)}{6}$$

Correction :

Pour $n$ dans ${\mathbb{N}}^{\ast }$, on note ${\mathcal{P}}_n$ la propriété :

$$1^2+2^2+3^2+\cdots +(n-1{)}^2+n^2=\frac{n(n+1)(2n+1)}{6}$$

Initialisation :

Dans cet exemple, $n$ est un entier naturel non nul. L’initialisation se fait donc pour $n=1$.

La vérification de ${\mathcal{P}}_1$ est immédiate. En effet,

$$1^2=1=\frac{1(1+1)(2\times 1+1)}{6}=\frac{1\times 2\times 3}{6}=1$$

Hérédite :

Fixons $n$ dans ${\mathbb{N}}^{\ast }$ tel que ${\mathcal{P}}_n$ soit vraie. On a donc :

$$1^2+2^2+3^2+\cdots +(n-1{)}^2+n^2=\frac{n(n+1)(2n+1)}{6}$$

Puisque,

$$1^2+2^2+3^2+\cdots +(n-1{)}^2+n^2+(n+1{)}^2=(1^2+2^2+3^2+\cdots +(n-1{)}^2+n^2)+(n+1{)}^2$$

Alors, grâce à ${\mathcal{P}}_n$ on a,

$$\begin{array}{rl}{1}^2+2^2+3^2+\cdots +(n-1{)}^2+n^2+(n+1{)}^2& =\frac{n(n+1)(2n+1)}{6}+(n+1{)}^2\\ & =\frac{(n+1)(n(2n+1)+6(n+1))}{6}\\ & =\frac{(n+1)(2n^2+7n+6)}{6}\end{array}$$

Par ailleurs, l’équation ${\displaystyle 2n^2+7n+6=0}$ d’inconnue $n\in \mathbb{N}$ a pour discriminant $7^2-4\times 2\times 6=1$ strictement positif. Elle possède donc deux solutions, à savoir $-2$ et ${\displaystyle -\frac{3}{2}}$.

Le polynôme ${\displaystyle 2n^2+7n+6=0}$ se factorise donc sous la forme ${\displaystyle 2(n+2)(n+\frac{3}{2})}$ soit ${\displaystyle (n+2)(2n+3)}$.

On en déduit que,

$$\begin{array}{rl}{1}^2+2^2+3^2+\cdots +(n-1{)}^2+n^2+(n+1{)}^2& =\frac{(n+1)(n+2)(2n+3)}{6}\\ & =\frac{(n+1)(n+2)(2(n+1)+1)}{6}\end{array}$$

C’est exactement ${\mathcal{P}}_{n+1}$. ${\mathcal{P}}_{n+1}$ est donc vraie.

On peut donc conclure que la propriété ${\mathcal{P}}_n$ est vraie pour tout $n$.

C’est à dire que pour tout $n\in {\mathbb{N}}^{\ast }$, on a :

$${\displaystyle 1^2+2^2+3^2+\cdots +(n-1{)}^2+n^2=\frac{n(n+1)(2n+1)}{6}}$$

 

— EXEMPLE 3 —

Une inégalité.

Montrer par récurrence que pour tout entier naturel $n\ge 6$, on a :

$$2^n\ge (n+2{)}^2$$

Correction :

Pour tout entier naturel $n\ge 6$, on note ${\mathcal{P}}_n$ la propriété :

$$2^n\ge (n+2{)}^2$$

Initialisation :

Dans cet exemple, $n$ est un entier naturel supérieur ou égal à $6$. L’initialisation se fait donc pour $n=6$.

On a $2^6=64\ge (6+2{)}^2=64$ donc ${\mathcal{P}}_6$ est vraie.

(On vérifie aisément que ${\mathcal{P}}_n$ est fausse pour $n=0,1,2,3,4$ et $5$.)

 

Hérédite :

Fixons $n\ge 6$ tel que ${\mathcal{P}}_n$ soit vraie. On a donc :

$$2^n\ge (n+2{)}^2$$

Puisque,

$$2^{n+1}=2\times 2^n$$

Alors, grâce à ${\mathcal{P}}_n$ on a,

$$\begin{array}{rl}{2}^{n+1}& =2\times 2^n\\ & \ge 2\times (n+1{)}^2\end{array}$$

Pour montrer que ${\mathcal{P}}_{n+1}$ est vraie, c’est à dire que ${\displaystyle 2^{n+1}\ge (n+3{)}^2}$, il suffit de montrer que ${\displaystyle 2(n+2{)}^2\ge (n+3{)}^2}$ ou encore, ${\displaystyle 2(n+2{)}^2–(n+3{)}^2\ge 0}$.

Or,

$$\begin{array}{rl}2(n+2{)}^2-(n+3{)}^2& =2n^2+8n+8-n^2-6n-9\\ & =n^2+2n-1\\ & =(n+1{)}^2-2\ge 0\text{pour }n\ge 6\end{array}$$

On a donc ${\displaystyle 2^{n+1}\ge (n+3{)}^2}$. Ainsi, ${\mathcal{P}}_{n+1}$ est vraie.

On peut donc conclure que la propriété ${\mathcal{P}}_n$ est vraie pour tout $n\ge 6$.

C’est à dire que pour tout entier naturel $n\ge 6$, on a : $2^n\ge (n+2{)}^2$.

 

— EXEMPLE 4 —

Inégalité de Bernoulli.

Soit $a$ un réel positif.

Montrer par récurrence que pour tout entier naturel $n$, on a :

$${\displaystyle (1+a{)}^n\ge 1+na}$$

Correction :

Pour $n$ dans $\mathbb{N}$, on note ${\mathcal{P}}_n$ la propriété :

$$(1+a{)}^n\ge 1+na$$

Initialisation :

On a $(1+a{)}^0=1$ donc,

$$1\ge 1+0\times a$$

La propriété ${\mathcal{P}}_0$ est vraie.

 

Hérédité :

Fixons $n$ dans $\mathbb{N}$ tel que ${\mathcal{P}}_n$ soit vraie. On a donc :

$$(1+a{)}^n\ge 1+na$$

Puisque,

$$(1+a{)}^{n+1}=(1+a{)}^n\times (1+a)$$

Alors, grâce à ${\mathcal{P}}_n$ on a,

$$(1+a{)}^{n+1}\ge (1+na)\times (1+a)$$

Mais,

$$\begin{array}{rl}(1+na)\times (1+a)& =1+a+na+n{a}^2\\ & =1+(n+1)a+n{a}^2\\ & \ge 1+(n+1)a\text{car }n{a}^2\ge 0\end{array}$$

Finalement,

$$(1+a{)}^{n+1}\ge 1+(n+1)a$$

C’est exactement ${\mathcal{P}}_{n+1}$. ${\mathcal{P}}_{n+1}$ est donc vraie.

On peut donc conclure que la propriété ${\mathcal{P}}_n$ est vraie pour tout $n$.

C’est à dire que pour tout réel positif $a$ et pour tout entier naturel $n$, on a : $(1+a{)}^n\ge 1+na$.

 

— EXEMPLE 5 —

Un peu d’arithmétique.

Montrer par récurrence que pour tout entier naturel $n$, ${\displaystyle {10}^n-1}$ est un multiple de $9$.

 

Correction :

Pour $n$ dans $\mathbb{N}$, on note ${\mathcal{P}}_n$ la propriété :

${\displaystyle {10}^n-1}$ est un multiple de $9$

Il existe donc un entier relatif $k$ tel que ${10}^n-1=9k$.

Initialisation :

On a ${10}^0-1=0$, c’est bien un multiple de $9$.

La propriété ${\mathcal{P}}_0$ est vraie.

Hérédité :

Fixons $n$ dans $\mathbb{N}$ tel que ${\mathcal{P}}_n$ soit vraie. On a donc :

${\displaystyle {10}^n-1}$ est un multiple de $9$.

Puisque,

$$\begin{array}{rl}{10}^{n+1}-1& =10\times {10}^n-1\\ & =10\times {10}^n-10+9\\ & =10({10}^n-1)+9\end{array}$$

Alros, grâce à ${\mathcal{P}}_n$ on a,

$$\begin{array}{rl}{10}^{n+1}-1& =10\times 9k+9\\ & =9(10k+1)\end{array}$$

C’est exactement ${\mathcal{P}}_{n+1}$. ${\mathcal{P}}_{n+1}$ est donc vraie.

On peut donc conclure que la propriété ${\mathcal{P}}_n$ est vraie pour tout $n$.

C’est à dire que pour tout entier naturel $n$, ${\displaystyle {10}^n-1}$ est un multiple de $9$.

 

— EXEMPLE 6 —

Avec des suites.

On considère la suite ${\displaystyle (u_n{)}_{n\in \mathbb{N}}}$ définie par $u_0=2$ et pour tout entier naturel $n$ par ${\displaystyle u_{n+1}=\frac{1}{2}{u}_n+2}$.

Montrer par récurrence que pour tout entier naturel $n$,

$$u_n\le 4$$

 

Correction :

Pour $n$ dans $\mathbb{N}$, on note ${\mathcal{P}}_n$ la propriété :

$$u_n\le 4$$

 

Initialisation :

La vérification de ${\mathcal{P}}_0$ est immédiate, et on a,

$$u_0=2\le 4$$

La propriété ${\mathcal{P}}_0$ est donc vraie.

 

Hérédité :

Fixons $n$ dans $\mathbb{N}$ tel que ${\mathcal{P}}_n$ soit vraie. On a donc :

$$u_n\le 4$$

Or,

$$u_{n+1}=\frac{1}{2}{u}_n+2$$

D’où grâce à ${\mathcal{P}}_n$,

$$\begin{array}{rl}{u}_{n+1}& \le \frac{1}{2}\times 4+2\\ & \le 4\end{array}$$

C’est exactement ${\mathcal{P}}_{n+1}$. ${\mathcal{P}}_{n+1}$ est donc vraie.

On peut donc conclure que la propriété ${\mathcal{P}}_n$ est vraie pour tout $n$.

C’est à dire que pour tout entier naturel $n$, $u_n\le 4$.

 

— EXEMPLE 7 —

Avec des sinus.

Soit $x$ un réel multiple de $2\pi$.

Montrer par récurrence que, pour tout entier natuel $n$ non nul :

$$S_n=\sin (x)+\sin (2x)+\cdots +\sin (nx)=\frac{\sin \left(\frac{(n+1)x}{2}\right)\sin \left(\frac{nx}{2}\right)}{\sin \left(\frac{x}{2}\right)}$$

 

Correction :

Pour $n$ dans ${\mathbb{N}}^{\ast }$, on note ${\mathcal{P}}_n$ la propriété :

$$\sin (x)+\sin (2x)+\cdots +\sin (nx)=\frac{\sin \left(\frac{(n+1)x}{2}\right)\sin \left(\frac{nx}{2}\right)}{\sin \left(\frac{x}{2}\right)}$$

 

Initialisation :

Pour $n=1$, on a :

$S_1=\sin (x)$ et ${\displaystyle \frac{\sin \left(\frac{(1+1)x}{2}\right)\sin \left(\frac{x}{2}\right)}{\sin \left(\frac{x}{2}\right)}=\sin (x)}$

La propriété ${\mathcal{P}}_1$ est donc vraie.

 

Hérédité :

Fixons $n$ dans ${\mathbb{N}}^{\ast }$ tel que ${\mathcal{P}}_n$ soit vraie. On a donc :

$$S_n=\frac{\sin \left(\frac{(n+1)x}{2}\right)\sin \left(\frac{nx}{2}\right)}{\sin \left(\frac{x}{2}\right)}$$

Puisque,

$$S_{n+1}=\sin (x)+\sin (2x)+\cdots +\sin (nx)+\sin ((n+1)x)$$

Alors, grâce à ${\mathcal{P}}_n$ on a,

$$\begin{array}{rl}{S}_{n+1}& =\sin (x)+\sin (2x)+\cdots +\sin (nx)+\sin ((n+1)x)\\ \\ & =\frac{\sin \left(\frac{(n+1)x}{2}\right)\sin \left(\frac{nx}{2}\right)}{\sin \left(\frac{x}{2}\right)}+\sin (2\times \frac{(n+1)x}{2})\\ & =\frac{\sin \left(\frac{(n+1)x}{2}\right)\sin \left(\frac{nx}{2}\right)}{\sin \left(\frac{x}{2}\right)}+2\sin \left(\frac{(n+1)x}{2}\right)\cos \left(\frac{(n+1)x}{2}\right)\\ & =\sin \left(\frac{(n+1)x}{2}\right)[\frac{\sin \left(\frac{nx}{2}\right)}{\sin \left(\frac{x}{2}\right)}+2\cos \left(\frac{(n+1)x}{2}\right)]\\ & =\sin \left(\frac{(n+1)x}{2}\right)\frac{\sin \left(\frac{nx}{2}\right)+2\cos \left(\frac{(n+1)x}{2}\right)\sin \left(\frac{x}{2}\right)}{\sin \left(\frac{x}{2}\right)}\end{array}$$

Par ailleurs, ${\displaystyle 2\sin (a)\cos (b)=\sin (a+b)+\sin (a-b)}$, d’où,

Avec, ${\displaystyle a=\frac{x}{2}}$ et ${\displaystyle b=\frac{(n+1)x}{2}}$,

$$2\cos \left(\frac{(n+1)x}{2}\right)\sin \left(\frac{x}{2}\right)=\sin \left(\frac{(n+2)x}{2}\right)-\sin \left(\frac{nx}{2}\right)$$

Soit,

$$S_{n+1}=\frac{\sin \left(\frac{(n+1)x}{2}\right)\sin \left(\frac{(n+2)x}{2}\right)}{\sin \left(\frac{x}{2}\right)}$$

C’est exactement ${\mathcal{P}}_{n+1}$. ${\mathcal{P}}_{n+1}$ est donc vraie.

On peut donc conclure que la propriété ${\mathcal{P}}_n$ est vraie pour tout $n$.

C’est à dire que pour tout entier naturel $n$ non nul,

$$\sin (x)+\sin (2x)+\cdots +\sin (nx)=\frac{\sin \left(\frac{(n+1)x}{2}\right)\sin \left(\frac{nx}{2}\right)}{\sin \left(\frac{x}{2}\right)}$$

 

— EXEMPLE 8 —

Une dernière inégalité …

Montrer par récurrence que pour tout entier naturel $n$ non nul, on a :

$$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{1}{n^2}\le 2-\frac{1}{n}$$

 

Correction :

Pour $n$ dans ${\mathbb{N}}^{\ast }$, on note ${\mathcal{P}}_n$ la propriété :

$$\mathrm{\forall }n\in {\mathbb{N}}^{\ast },1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{1}{n^2}\le 2-\frac{1}{n}$$

 

Initialisation :

On a,

$$1\le 2-\frac{1}{1}$$

La propriété ${\mathcal{P}}_1$ est vraie.

 

Hérédité :

Fixons $n$ dans ${\mathbb{N}}^{\ast }$ tel que ${\mathcal{P}}_n$ soit vraie. On a donc :

$$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{1}{n^2}\le 2-\frac{1}{n}$$

En ajoutant ${\displaystyle \frac{1}{(n+1{)}^2}}$ aux deux membres de l’inégalité, on obtient :

$$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{1}{n^2}+\frac{1}{(n+1{)}^2}\le 2-\frac{1}{n}+\frac{1}{(n+1{)}^2}$$

Pour montrer que ${\mathcal{P}}_{n+1}$ est vraie, c’est à dire que,

$$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{1}{n^2}+\frac{1}{(n+1{)}^2}\le 2-\frac{1}{n+1}$$

Il suffit de montrer que,

$$2-\frac{1}{n}+\frac{1}{(n+1{)}^2}\le 2-\frac{1}{n+1}$$

Ou encore,

$$2-\frac{1}{n}+\frac{1}{(n+1{)}^2}-(2-\frac{1}{n+1})\le 0$$

Or,

$$\begin{array}{rl}2-\frac{1}{n}+\frac{1}{(n+1{)}^2}-(2-\frac{1}{n+1})& =-\frac{1}{n}+\frac{1}{(n+1{)}^2}+\frac{1}{n+1}\\ & =\frac{-(n+1{)}^2+n+(n+1)}{n(n+1{)}^2}\\ & =\frac{-1}{n(n+1{)}^2}\\ & \le 0\end{array}$$

D’où,

$$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{1}{n^2}+\frac{1}{(n+1{)}^2}\le 2-\frac{1}{n}+\frac{1}{(n+1{)}^2}$$

Ainsi, ${\mathcal{P}}_{n+1}$ est vraie.

On peut donc conclure que la propriété ${\mathcal{P}}_n$ est vraie pour tout $n\in {\mathbb{N}}^{\ast }$.

C’est à dire que pour tout entier naturel $n\in {\mathbb{N}}^{\ast }$, on a,

$$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{1}{n^2}+\frac{1}{(n+1{)}^2}\le 2-\frac{1}{n}+\frac{1}{(n+1{)}^2}$$

III. Synthèse :

Le raisonnement par récurrence est un outil essentiel. Dans la plupart des exemples que vous serez amenés à traiter au lycée et en BAC+1, sa mise en oeuvre ne pose pas de difficultés. Il convient en revanche de rédiger soigneusement.

Pour effectuer une démonstration par récurrence, il est souvent utile d’avoir, au préalable, une idée du résultat que l’on veut prouver.

Dans ce contexte, il est pertinent de commencer par deviner le résultat en considérant les petites valeurs de $n$ comme à la question 1 de l’onglet « Le principe ». Mais cette phase « de tâtonnement » doit se poursuivre par une phase de démonstration comme vu dans les exemples (Onglet « Des exemples »)

 

En guise de conclusion,

Soit $n$ un entier naturel et ${\mathcal{P}}_n$ une propriété.

On peut dire que le raisonnement par récurrence repose sur le principe suivant :

Si $\underset{\text{Initialisation}}{\underbrace{{\mathcal{P}}_0\text{ est vraie}}}$ et si : $\underset{\text{Hérédité}}{\underbrace{\mathrm{\forall }n\in \mathbb{N},{\mathcal{P}}_n⟹{\mathcal{P}}_{n+1}}},$ alors : $\mathrm{\forall }n\in \mathbb{N},{\mathcal{P}}_n$.

 

Voici une proposition de rédaction quand on veut montrer une propriété par récurrence :

On énonce la propriété à démontrer : $\mathrm{\forall }n\in \mathbb{N},{\mathcal{P}}_n$.

• Initialisation : On vérifie que ${\mathcal{P}}_0$ est vraie.

• Hérédité : On fixe $n$ dans $\mathbb{N}$ tel que ${\mathcal{P}}_n$ soit vraie et on démontre que ${\mathcal{P}}_{n+1}$ est vraie.

• Conclusion.

 

FIN