L’objectif du raisonnement par récurrence est de démontrer qu’une propriété faisant intervenir des entiers naturels est vrai.

La rédaction d’une démonstration utilisant ce principe de récurrence est très normalisée et il est important de bien l’appliquer :

On commence par nommer $P_n$ la propriété à démontrer. Puis on rédige le raisonnement avec les trois phases suivantes dans l’ordre :

• Initialisation : *“*On vérifie que la propriété est vrai pour la plus petite valeur de $n$ $$”
• Hérédité : “On suppose qu’il existe $n > n_0$ tel que $P_n$ est vrai, montrons qu’alors $P_{n+1}$ est vrai.
• Conclusion : “La propriété étant initialisé et hérédité est vrai pour $n > n_0$.

Démonstration :

Soit $(Un)$ défini par : $\begin{cases} u_1 = 1\\u_{n+1} = 2u_n + 1\end{cases}$

Démontrer que $\forall n \in \mathbb{N*}, u_n = 2^n - 1$.

• On vérifie que $P_n$ est vrai pour $n = 1$

  • D’une part, $u_1 = 1$
  • D’autre part, $2^1 -1 = 1$
  • Donc $P_0$ est vérifié.

• On suppose qu’il existe $n > 0$ tel que $P_n$ est vrai, montrons qu’alors $P_{n+1} : u_{n+1} = 2^{n+1} -1$ est vrai.

  $$ \begin{align*} u_n &= 2^n - 1\\u_{n+1} &= 2u_n + 1\\u_{n+1} &= 2(2^n - 1) + 1\\u_{n+1} &= 2^{n+1} -2 + 1\\u_{n+1} &= 2^{n+1} - 1 \quad \text{cqfd}\end{align*} $$

• La propriété étant initialisé et hérédité est vrai pour $n > 1$.