La démonstration par récurrence

I- Introduction

Le raisonnement par récurrence est utilisé pour montrer des résultats faisant intervenir une variable entière de l'ensemble $\mathbb{N}$ ou d'une partie de cet ensemble, comme par exemple $\mathbb{N}^{}$, $\mathbb{N}^{}-\lbrace 1,2 \rbrace$, etc.

Cette démonstration s'effectue en trois étapes :

L'étape initialisation : Montrer que le résultat est vrai pour le tout premier rang (en général le premier rang est 0, mais il se peut que le premier rang soit 1, 2 ou autre, cela dépend du résultat à démontrer).

L'étape hérédité : Montrer que le résultat est héréditaire, c'est-à-dire montrer que le résultat peut être "transmis" d'un rang fixé quelconque $k$ au rang suivant $k+1$.

La conclusion.

Pour expliquer ce principe assez intuitivement, prenons les deux exemples suivants :

Exemple 1 : La file de dominos

Si l'on pousse le premier domino de la file (Initialisation).
Et si les dominos sont posés l'un après l'autre d'une manière à ce que la chute d'un domino entraîne la chute de son suivant (Hérédité). Sauf s'il y a un trou...
Alors : Tous les dominos de la file tombent. (la conclusion)

Exemple 2 : L'échelle
Si on sait monter le premier barreau de l'échelle (Initialisation).
Et si l'on sait toujours passer d'un barreau au barreau qui le suit (Hérédité).
Alors : On peut monter l'échelle. (la conclusion)

II. Le principe de la démonstration par récurrence

Cette démonstration s’applique lorsque l’on cherche à démontrer qu’une propriété dépendant d’un entier naturel $n$ est vraie pour tout entier $n \geq n_0$, $n_0$ étant un entier naturel donné.

On procède en trois étapes :

Étape n°1 : Initialisation

On montre que la propriété est vraie pour $n = n_0$ (au rang $n_0$).

Étape n°2 : Hérédité

On démontre que :
Si la propriété est supposée vraie pour un entier naturel $n$ supérieur ou égal à $n_0$ (ceci s’appelle l’hypothèse de récurrence), alors elle est vraie pour l’entier suivant $n + 1$.
On veut donc montrer que, si elle est vraie à un rang $n$, elle est aussi vraie au rang suivant $n + 1$.

Étape n°3 : Conclusion

On combine les étapes 1 et 2 :
La propriété est vraie au rang $n_0$ (étape n°1) et elle est héréditaire à partir du rang $n_0$ (étape n°2), donc le principe de récurrence permet de conclure que la propriété est vraie pour n’importe quel entier naturel $n \geq n_0$.

Montrer une égalité par récurrence

Énoncé : On considère la suite $(u_n){n \in \mathbb{N}}$ définie par $u_0 = 2$ et, pour tout entier naturel $n$, $u_{n+1} = 3 u_n$. Montrer par récurrence que : $\forall n \in \mathbb{N},\ u_n = 2 \times 3^n$

Initialisation :
Vérifions que la propriété est vraie au rang $0$.
$u_0 = 2$ et $2 \times 3^0 = 2 \times 1 = 2 = u_0$
Donc, la propriété est vraie au rang $0$.

Hérédité :
On suppose qu’il existe un entier naturel $n$ tel que $P_n$ est vraie, c'est-à-dire $u_n = 2 \times 3^n$.
Montrons que $P_{n+1}$ est vraie, c'est-à-dire $u_{n+1} = 2 \times 3^{n+1}$.

Par définition de la suite $(u_n){n \in \mathbb{N}}$, on a : $u_{n+1} = 3 u_n$

Mais d’après l’hypothèse de récurrence, on a :
$u_n = 2 \times 3^n$.

Donc :
$u_{n+1} = 3 u_n = 3 \times 2 \times 3^n = 2 \times 3^{n+1}$.

La propriété est héréditaire.

Conclusion :
La propriété est vraie au rang $0$ et elle est héréditaire. Donc, d’après le principe de récurrence, elle est vraie pour tout entier naturel $n$.

Montrer une inégalité par récurrence

Énoncé :
On considère la suite $(p_n)_{n \in \mathbb{N}}$ définie par $p_1 = 1$ et, pour tout entier naturel non nul, $p_{n+1} = 0,5 p_n + 0,4$. Montrer par récurrence que : $\forall n \in \mathbb{N},\ p_n \gt 0,8$

Initialisation :
On a : $p_1 = 1 \gt 0,8$
Donc, la propriété est vraie au rang $1$.

Hérédité :
Soit $n \geq 1$.
On suppose que $H_n$ est vraie, c'est-à-dire : $p_n \gt 0,8$.
Montrons que $H_{n+1}$ est vraie, c'est-à-dire : $p_{n+1} \gt 0,8$.

D’après l’hypothèse de récurrence :
$p_n \gt 0,8$ $\Rightarrow 0,5 p_n \gt 0,4$

${\phantom{p_n \gt 0,8}\Rightarrow 0,5 p_n + 0,4 \gt 0,8}$

${\phantom{p_n \gt 0,8}\Rightarrow p_{n+1} \gt 0,8}$

La propriété est donc héréditaire.

Conclusion :
La propriété est vraie au rang $1$ et elle est héréditaire. Donc, d’après le principe de récurrence, elle est vraie pour tout entier naturel $n \geq 1$.