Raisonnement par récurrence

Définition intuitive

Le raisonnement par récurrence consiste à montrer que la propriété est vraie pour le premier entier, puis qu’elle se transmet d’un entier au suivant, comme une rangée de dominos : si le premier tombe et que chacun fait tomber le suivant, alors ils tombent tous.

Définition formelle

Il existe trois types de raisonnement par récurrence : la récurrence simple, la récurrence double et la récurrence forte.

1. $\textbf{Raisonnement par récurrence simple}$

Soit $n_0\in\mathbb{N}$ et $(P(n))_{n\ge n_0}$ une suite de propositions.
Si on a établi que :

• $\textbf{Initialisation :}$ $P(n_{0})$ est vraie.
• $\textbf{Hérédité :}$ Pour tout entier $n\geqslant n_{0}$, $P(n)\ \Rightarrow\ P(n+1).$

Alors pour entier $n\geqslant n_{0}$, $P(n)$ est vraie.

2. $\textbf{Raisonnement par récurrence double}$

Soit $n_0\in\mathbb{N}$ et $(P(n))_{n\ge n_0}$ une suite de propositions.
Si on a établie que :

• $\textbf{Double initialisation :}$ $P(n_{0})$ et $P(n_{0}+1)$ sont vraies.
• $\textbf{Double hérédité :}$ Pour tout entier $n\geqslant n_{0}$, $\big[ \, P(n) \, \text{et} \, P(n+1) \big] \Rightarrow\ P(n+2).$

Alors pour entier $n\geqslant n_{0}$, $P(n)$ est vraie.

3. $\textbf{Raisonnement par récurrence forte}$

Soit $n_0\in\mathbb{N}$ et $(P(n))_{n\ge n_0}$ une suite de propositions.
Si on a établie que :

• $\textbf{Initialisation :}$ $P(n_{0})$ est vraie.
• $\textbf{Hérédité forte:}$ Pour tout entier $n\geqslant n_{0}$, $\big[ \, \forall k\in \llbracket n_{0},n \rrbracket ,\, P(k) \big] \Rightarrow\ P(n+1).$

Alors pour entier $n\geqslant n_{0}$, $P(n)$ est vraie.

Exemple de rédaction pour le raisonnement par récurrence simple :

Pour $n\in \mathbb{N}$ tel que $n\geqslant n_{0}$, notons $P(n)=$ « Ici la proposition, à écrire, et dépendant de $n$ » , et montrons que $P(n)$ est vraie par récurrence simple.

• $\textbf{Initialisation :}$ Ici on montre (sauf si c’est évident) et on écrit explicitement que $P(n_{0})$ est vraie.
• $\textbf{Hérédité :}$ Soit $n \in \mathbb{N}$ tel que $n\geqslant n_{0}$, supposons que $P(n)$ est vraie. Montrons que $P(n+1)$ est vraie.
  $$...$$$$\text{Démonstration de } P(n+1)$$$$...$$Donc $P(n+1)$ est vraie.

$\textbf{Conclusion :}$ Donc $\forall n \in \mathbb{N}$ tel que $n\geqslant n_0$, $P(n)$ est vraie.

$\textbf{Remarque pour la rédaction :}$

• Le rang $n_0$ est souvent donné par l’énoncé mais cela peut être à vous de le déterminer.
• Il n’est pas nécessaire d’écrire Initialisation, Hérédité, Conclusion dans la rédaction.

$\textbf{Attention :}$ Dans la proposition $P(n)$, on ne doit surtout par écrire : $\forall n\in \mathbb{N}$ tel que $n\geqslant n_{0}$.
En effet, $P(n)$ dépend déjà de $n$ donc écrire cela serait complétement faux.