Une récurrence qui regarde deux rangs en arrière

Ce qu'on montre. L'égalité $u_n=2^n$. La relation fait intervenir deux rangs antérieurs : la propriété à propager doit donc en porter deux.

Posons, pour $n\in \mathbb{N}$, $\mathcal{P}(n)$ : « $u_n=2^n$ et $u_{n+1}=2^{n+1}$ ».

Initialisation. $u_0=1=2^0$ et $u_1=2=2^1$ : $\mathcal{P}(0)$ est vraie.

Hérédité. Soit $n\in \mathbb{N}$ fixé tel que $\mathcal{P}(n)$ soit vraie. Alors $u_{n+1}=2^{n+1}$ est déjà la première moitié de $\mathcal{P}(n+1)$. Pour la seconde, la relation de récurrence donne $$u_{n+2}=3u_{n+1}-2u_n=3\times 2^{n+1}-2\times 2^n=3\times 2^{n+1}-2^{n+1}=2\times 2^{n+1}=2^{n+2},$$ où l'on a utilisé les deux égalités de $\mathcal{P}(n)$. Donc $\mathcal{P}(n+1)$ est vraie.

Conclusion. Par récurrence, $\mathcal{P}(n)$ est vraie pour tout $n$, donc en particulier $u_n=2^n$ pour tout $n\in \mathbb{N}$.

Pourquoi deux rangs. L'hérédité consomme $u_n$ et $u_{n+1}$ pour produire $u_{n+2}$. Une propriété ne portant que sur $u_n$ ne fournirait pas $u_{n+1}$, et le calcul de $u_{n+2}$ resterait bloqué. On dit qu'on effectue une récurrence double : on emballe deux rangs dans une seule propriété, ce qui oblige à vérifier deux valeurs à l'initialisation.

Contrôle. $u_2=3\times 2-2\times 1=4=2^2$, $u_3=3\times 4-2\times 2=8=2^3$.