Le raisonnement par récurrence

Démontrer par récurrence, c'est prouver qu'une proposition est vraie pour tout entier $n$ supérieur ou égal à un entier naturel fixé $n_0$ . Et pour cela, on doit voir si elle est vraie au rang $n+1$ . On parle alors d'hérédité. Dire qu'une proposition $\mathcal{P}_n$ est héréditaire à partir de $n_0$ signifie que, si $n\geq n_0$ et si $\mathcal{P}_n$ est vraie, alors $\mathcal{P}_{n+1}$ est vraie. Il y a trois étapes indispensable dans la démonstration par récurrence : pour commencer, il faut obligatoirement nommer la proposition. On note $\mathcal{P}_{n}$ la proposition...

Initialisation : montrons que $\mathcal{P}_{n_0}$ est vraie.
Hérédité : supposons qu'il existe un entier $n\geq n_0$ tel que $\mathcal{P}_{n}$ soit vraie. Démontrons que $\mathcal{P}_{n+1}$ est vraie. Cette supposition est appelée "hypothèse de récurrence".
Conclusion : $\mathcal{P}_{n}$ est héréditaire à partir de $n_0$ et $\mathcal{P}_{n_0}$ est vraie, donc $\mathcal{P}_{n}$ est vraie pour tout entier naturel $n\geq n_0$ .

Mise en pratique. On considère la suite $(u_n)$ définie par : $u_0=0$ et pour tout entier naturel $n$ :

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

La démonstration par récurrence permet de définir la forme explicite d'une suite définie par récurrence.

Il est nécessaire de calculer les premiers termes de la suite pour émettre une conjecture sur la forme explicite. Après calcul, on obtient :

$\\ n=0\ ; u_0=0\\\\ n=1\ ; u_1=\frac{1}{2-0}=\frac{1}{2}\\\\ n=2\ ; u_2=\frac{1}{2-\frac{1}{2}}=\frac{2}{3}\\\\ n=3\ ; u_3=\frac{1}{2-\frac{2}{3}}=\frac{3}{4}$

Il semblerait que :

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

Posons la propriété $\mathcal{P}_n$ : $``u_n=\frac{n}{n+1}"$ pour tout $n \in \mathbb{N}$ .

Initialisation : montrons que $\mathcal{P}_0$ est vraie.

$u_0=0$ (par définition)

$\frac{0}{0+1}=0$

La proposition $\mathcal{P}_n$ est vérifiée au rang 0.

Hérédité : supposons qu'il existe un entier $n\geq n_0$ tel que $\mathcal{P}_n$ soit vraie. Démontrons que $\mathcal{P}_{n+1}$ est vraie, c'est-à-dire :

$\mathcal{P}_{n+1} : `` u_{n+1}=\frac{n+1}{n+2} "$

On a, par hypothèse de récurrence :

$u_n=\dfrac{n}{n+1}$

On sait que :

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

Ainsi, en remplaçant :

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

La proposition est vérifiée au rang $n+1$ .

Conclusion : la proposition est vraie au rang 0 et est héréditaire au rang 0, donc la proposition est vraie pour tout entier naturel $n$ .