Raisonnement par récurrence (simple, double, forte) — MPSI à PTSI

Pour démontrer une propriété $P(n)$ pour tout entier $n \geq n_0$.

Simple : $P(n) \Rightarrow P(n+1)$ Double : $P(n)$ et $P(n+1) \Rightarrow P(n+2)$ Forte : $P(n_0),\dots,P(n) \Rightarrow P(n+1)$

1. Énoncer clairement $P(n)$.
2. Initialisation : vérifier $P(n_0)$ (et $P(n_0+1)$ en récurrence double).
3. Hérédité : fixer $n$, supposer l'hypothèse, prouver le rang suivant.
4. Conclure pour tout $n \geq n_0$.

$u_0=u_1=1$, $u_{n+2}=u_{n+1}+u_n$ : $u_n \geq 1$ : Initialisation : $u_0, u_1 \geq 1$. ; Si $u_n, u_{n+1} \geq 1$ alors $u_{n+2} \geq 2 \geq 1$. ⇒ Récurrence double : $u_n \geq 1$ pour tout $n$.

Une hérédité sans initialisation ne prouve rien ; en récurrence double, il faut deux initialisations.