Révisions d’été – Le raisonnement par récurrence (Partie I)

Le principe

I. Le principe de récurrence :

Soit $n$ un entier naturel.

On considère les suites $\displaystyle (u_n)_{n\in\mathbb{N}}$ et $\displaystyle (v_n)_{n\in\mathbb{N}}$ de terme général :

$\displaystyle u_n=0+1+2+\cdots +(n-1)+n=\frac{n(n+1)}{2}\quad$ et,

$\displaystyle v_n=0^3+1^3+2^3+\cdots +(n-1)^3+n^3$.

1. Calculer $u_n$ et $v_n$ pour $n=0,\,1,\,2,\,3$ et $4$.

Peut-on conjecturer une relation entre $u_n$ et $v_n$ ?

2. Considérons la propriété $\mathcal{P}_n$ : $u_{n}^2=v_n$.

2.1. $\mathcal{P}_0$ est-elle vraie ?

2.2. Supposons que pour un certain entier $n$, $\mathcal{P}_n$ soit vraie.

Justifier les égalités :

$$\begin{align}v_{n+1}&=\frac{n^2(n+1)^2}{4}+(n+1)^3\\&=\frac{(n+1)^2(n+2)^2}{4}\end{align}$$

3. La propriété $\mathcal{P}_{n+1}$ est-elle vraie ?

 

Correction

1. Calcul de $u_n$ et $v_n$ pour $n=0,\,1,\,2,\,3$ et $4$ :

On a,

$\displaystyle\begin{cases}u_0=0\\v_0=0\end{cases}$,

$\displaystyle\begin{cases}u_1=\frac{1(1+1)}{2}=1\\v_1=1^3=1\end{cases}$,

$\displaystyle\begin{cases}u_2=\frac{2(2+1)}{2}=3\\v_2=1^3+2^3=9\end{cases}$,

$\displaystyle\begin{cases}u_3=\frac{3(3+1)}{2}=6\\v_3=1^3+2^3+3^3=36\end{cases}$, et

$\displaystyle\begin{cases}u_4=\frac{4(4+1)}{2}=10\\v_3=1^3+2^3+3^3+4^3=100\end{cases}$

On remarque que :

$u_{0}^2=v_0$, $u_{1}^2=v_1$, $u_{2}^2=v_2$, $u_{3}^2=v_3$ et $u_{4}^2=v_4$.

On peut conjecturer que pour tout entier naturel $n$, on a la relation : $u_{n}^2=v_n$.

 

2. Considérons la propriété $\mathcal{P}_n$ : $u_{n}^2=v_n$.
2.1. $\mathcal{P}_0$ est-elle vraie ?

La vérification $\mathcal{P}_0$ est immédiate.

$$u_{0}^2=0=v_0$$

 

2.2. Supposons que pour un certain entier $n$, $\mathcal{P}_n$ soit vraie. Justifier les égalités :

$$v_{n+1}=\frac{n^2(n+1)^2}{4}+(n+1)^3=\frac{(n+1)^2(n+2)^2}{4}$$

On a,

$$\begin{align}v_{n+1}&=0^3+1^3+2^3+\cdots +(n-1)^3+n^3\\&=v_n+(n+1)^3\end{align}$$

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

$$\begin{align}v_{n+1}&=u_{n}^2+(n+1)^3\\&=\left(\frac{n(n+1)}{2}\right)^2+(n+1)^3\\&=\frac{n^2(n+1)^2}{4}+(n+1)^3\end{align}$$

Mais encore,

$$\begin{align}v_{n+1}&=\frac{n^2(n+1)^2+4(n+1)^3}{4}\\&=\frac{(n+1)^2(n^2+4n+4)}{4}\\&=\frac{(n+1)^2(n+2)^2}{4}\end{align}$$

3. Véracité de la propriété $\mathcal{P}_{n+1}$ ?

Pour $n$ dans $\mathbb{N}$, on a $\mathcal{P}_{n+1}$ : $u_{n+1}^2=v_{n+1}$.

Puisque,

$$\begin{align}u_{n+1}^2&=\left(\frac{(n+1)(n+1+1)}{2}\right)^2\\&=\frac{(n+1)^2(n+2)^2}{4}\\&=v_{n+1}\end{align}$$

Alors, la propriété $\mathcal{P}_{n+1}$ est vraie.

Les résultats précédents nous amènent à conclure que $\mathcal{P}_{n}$ est vraie pour tout $n$.

La démarche que nous venons d’esquisser s’appelle « le raisonnement par récurrence ».

 

Observons son organisation en deux étapes :

Etape 1 :

On montre que la propriété $\mathcal{P}_{n}$ est vraie pour $n=0$ : $\mathcal{P}_{0}$ est vraie.

Cette étape s’appelle l’initialisation.

Il se peut que l’on demande de prouver la validité de $\mathcal{P}_{n}$ pour tout $n$ dans $\mathbb{N}^*$ (Exemple $2$) voire pour tout $n\geq n_0$ (Exemple $3$), l’initialisation consiste alors en la vérification de $\mathcal{P}_{1}$ ou $\mathcal{P}_{n_0}$.

Etape 2 :

On montre que si la propriété $\mathcal{P}_{n}$ est vraie au rang $n$, alors elle est vraie au rang suivant $n+1$. On dit que la propriété $\mathcal{P}_{n}$ est héréditaire.

Cette étape s’appelle l’hérédité.

Dans ces conditions, on pourra conclure que la propriété $\mathcal{P}_{n}$ est vraie pour tout entier naturel $n$.

Des exemples

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 :

$$\forall n\in\mathbb{N}\,,\quad 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{align}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{align}$$

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 :

$$\forall n\in\mathbb{N}^*\,,\quad 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}^*$, 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}^*$ 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{align}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{align}$$

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)\left(n+\frac{3}{2}\right)$ soit $\displaystyle (n+2)(2n+3)$.

On en déduit que,

$$\begin{align}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{align}$$

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 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\geq 6$, on a :

$$2^n\geq (n+2)^2$$

Correction :

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

$$2^n\geq (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\geq (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\geq 6$ tel que $\mathcal{P}_{n}$ soit vraie. On a donc :

$$2^n\geq (n+2)^2$$

Puisque,

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

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

$$\begin{align}2^{n+1}&=2\times 2^n\\&\geq 2\times (n+1)^2\end{align}$$

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

Or,

$$\begin{align}2(n+2)^2-(n+3)^2&=2n^2+8n+8-n^2-6n-9\\&=n^2+2n-1\\&=(n+1)^2-2\geq 0\quad\text{pour }n\geq 6\end{align}$$

On a donc $\displaystyle 2^{n+1}\geq (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\geq 6$.

C’est à dire que pour tout entier naturel $n\geq 6$, on a : $2^n\geq (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\geq 1+na$$

Correction :

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

$$(1+a)^n\geq 1+na$$

Initialisation :

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

$$1\geq 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\geq 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}\geq (1+na)\times (1+a)$$

Mais,

$$\begin{align}(1+na)\times (1+a)&=1+a+na+na^2\\&=1+(n+1)a+na^2\\&\geq 1+(n+1)a\quad\text{car }na^2\geq 0\end{align}$$

Finalement,

$$(1+a)^{n+1}\geq 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\geq 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{align}10^{n+1}-1&=10\times 10^n-1\\&=10\times 10^n-10+9\\&=10(10^n-1)+9\end{align}$$

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

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

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\leq 4$$

 

Correction :

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

$$u_n\leq 4$$

 

Initialisation :

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

$$u_0=2\leq 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\leq 4$$

Or,

$$u_{n+1}=\frac{1}{2}u_n+2$$

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

$$\begin{align}u_{n+1}&\leq\frac{1}{2}\times 4+2\\&\leq 4\end{align}$$

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\leq 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}^*$, 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}^*$ 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{align}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\left(2\times\frac{(n+1)x}{2}\right)\\&=\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)\left[\frac{\sin\left(\frac{nx}{2}\right)}{\sin\left(\frac{x}{2}\right)}+2\cos\left(\frac{(n+1)x}{2}\right)\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{align}$$

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}\leq 2-\frac{1}{n}$$

 

Correction :

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

$$\forall n\in\mathbb{N}^*\,,\quad 1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{1}{n^2}\leq 2-\frac{1}{n}$$

 

Initialisation :

On a,

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

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

 

Hérédité :

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

$$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{1}{n^2}\leq 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}\leq 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}\leq 2-\frac{1}{n+1}$$

Il suffit de montrer que,

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

Ou encore,

$$2-\frac{1}{n}+\frac{1}{(n+1)^2}-\left(2-\frac{1}{n+1}\right)\leq 0$$

Or,

$$\begin{align}2-\frac{1}{n}+\frac{1}{(n+1)^2}-\left(2-\frac{1}{n+1}\right)&=-\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}\\&\leq 0\end{align}$$

D’où,

$$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{1}{n^2}+\frac{1}{(n+1)^2}\leq 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}^*$.

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

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

Synthèse

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 $\underbrace{\mathcal{P}_0 \text{ est vraie}}_{\text{Initialisation}}\qquad$ et si : $\qquad\underbrace{\forall n\in\mathbb{N},\quad\mathcal{P}_n\,\Longrightarrow\, \mathcal{P}_{n+1}}_{\text{Hérédité}}\,,\qquad$ alors : $\qquad\forall n\in\mathbb{N},\quad\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 : $\forall n\in\mathbb{N},\quad\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

3 réflexions sur “Révisions d’été – Le raisonnement par récurrence (Partie I)”

  1. merci d’abord pour les efforts déployés, j’ai une tout petite remarque portant sur l’étape 2 (hérédité), en effet cette l’étape comporte encore deux sous étapes
    1- FIXATION: il s’agit de fixer au préalable un entier naturel n >=n0 puis supposer que P(n) est vrai pour ce même entier (HYPOTHESE DE RECURRENCE)
    2- HERIDITE: montrer que P(n+1) est vrai
    NB: cette remarque surmonte une difficulté pédagogique mais n’ajoute rien au raisonnement mathématique que tu as suggéré car je le trouve très excellent

  2. Bonsoir Mohamed et merci pour ton message.
    Je te prie d’abord de m’excuser pour ma réponse tardive – J’étais malade ces derniers jours et je suis toujours en convalescence –

    Tu as bien raison de nuancer les étapes de l’hérédité :)

    Une autre erreur assez répandue est qu’il arrive que l’on suppose que $\displaystyle\mathcal{P}_{n}$ est vraie pour un certain $n\in\mathbb{N}$.
    Le problème ici est que la proposition « $\displaystyle\mathcal{P}_{n}$ est vraie pour un certain $n\in\mathbb{N}$ » s’écrit en langage mathématique :
    $$\displaystyle\exists n\in\mathbb{N}\,\text{tel que}\quad\mathcal{P}_{n}$$
    alors que l’hérédité repose sur :
    $$\forall n\in\mathbb{N}\,,\quad \mathcal{P}_{n}\Rightarrow\mathcal{P}_{n+1}$$
    ;-)

  3. Bonjour à tous,
    dans la famille des erreurs à ne pas reproduire, en voici une que je rencontre régulièrement dans les copies.

    Lors de l’étape d’hérédité, il est fréquent de voir dans les copies des rédactions du type : Supposons que $\forall n\in\mathbb{N}$, $\mathcal{P}_{n}$ et montrons que $\mathcal{P}_{n+1}$ est vérifiée.
    On ne peut pas supposer la propriété vraie pour tout $n$ car c’est ce que l’on cherche à démontrer.

    bonne journée.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *


*

Retour en haut