Récurrence double : énoncé (MPSI)
Récurrence double
Soit $n_0\in\mathbb{N}$ et $P(n)$ une assertion pour $n\geq n_0$. On suppose :
- $P(n_0)$ et $P(n_0+1)$ sont vraies ;
- pour tout $n\geq n_0$, $\big(P(n)\ \text{et}\ P(n+1)\big)\Rightarrow P(n+2)$.
Alors $P(n)$ est vraie pour tout $n\geq n_0$.
Démonstration : Récurrence double
Preuve
Pour $n\geq n_0$, notons $Q(n)$ l'assertion « $P(n)$ et $P(n+1)$ ». On montre $Q$ par récurrence simple.
$Q(n_0)$ est vraie par hypothèse. Soit $n\geq n_0$ tel que $Q(n)$ soit vraie : $P(n)$ et $P(n+1)$ sont vraies, donc $P(n+2)$ aussi par hypothèse. Ainsi $P(n+1)$ et $P(n+2)$ sont vraies, c'est-à-dire $Q(n+1)$.
Par récurrence simple, $Q(n)$ est vraie pour tout $n\geq n_0$, donc en particulier $P(n)$.
Suite récurrente linéaire d'ordre 2
Soit $(u_n)$ définie par $u_0=2$, $u_1=3$ et $u_{n+2}=3u_{n+1}-2u_n$ pour tout $n\in\mathbb{N}$. Montrons que $u_n=2^n+1$ pour tout $n\in\mathbb{N}$. Notons $P(n)$ : $u_n=2^n+1$.
Initialisation. $2^0+1=2=u_0$ et $2^1+1=3=u_1$ : $P(0)$ et $P(1)$ sont vraies.
Hérédité. Soit $n\in\mathbb{N}$ tel que $P(n)$ et $P(n+1)$ soient vraies. Alors $$u_{n+2}=3\big(2^{n+1}+1\big)-2\big(2^n+1\big)=3\cdot 2^{n+1}-2^{n+1}+3-2=2\cdot 2^{n+1}+1=2^{n+2}+1.$$ Donc $P(n+2)$ est vraie.
Conclusion. Par récurrence double, $u_n=2^n+1$ pour tout $n\in\mathbb{N}$. Une récurrence simple ne suffit pas : le calcul de $u_{n+2}$ utilise deux termes précédents, et il faut deux initialisations.
S’entraîner
- Comparer $2^n$ et $n^2$
- Suites récurrentes d'ordre 2
- Affranchir avec des timbres de 3 et 5
- Écriture unique $n=2^a(2b+1)$
- Examen : suite de Fibonacci et récurrences