Récurrence (forte) fausse - partie 2

Nous allons maintenant illustrer une erreur commune sur la récurrence forte.

Soit $(u_n)_{n\geq 0}$ définie par $u_0:=2$, $u_1:=10$

\[u_{n+2}:= 5u_{n+1}- 6 u_n,\]

pour tout $n\geq 0$. 

Nous allons "montré" par récurrence que $u_n= 3\times 2^n - 3^n$, pour tout $n\geq 0$. (ce qui est faux pour $n=1$ !)

Preuve :

Soit $n\geq 0$, on pose $P_n$:= " $u_{k} = 3\times 2^k - 3^k$ pour tout $0\leq k\leq n$"

Initialisation : 

$u_0= 2$ et $3\times 2^0 - 3^0= 3-1=2$. Donc $P_0$ est vraie.

Hérédité : Soit $n\geq 0$. Montrons que si $P_n$ est vraie alors $P_{n+1}$ aussi.

Par définition de $(u_n)_n$, on a :

$u_{n+1}= 5 u_n - 6 u_{n-1} = 5 \times (3\times 2^n - 3^n) - 6 \times (3\times 2^{n-1} - 3^{n-1})$, car $u_{k} = 3\times 2^k - 3^k$ pour tout $0\leq k\leq n$. 

Cela donne alors

$u_{n+1}= (15-3\times 3) \times 2^n - (5 - 2)\times 3^n = 3 \times 2^{n+1} - 3^{n+1}$. 

On a donc que $P_{n+1}$ est vraie.   

Conclusion : $P_n$ est vraie pour tout $n\geq 0$. 

En particulier, on a que $u_n= 3\times 2^n - 3^n$, pour tout $n\geq 0$.

---

Attention spoiler !

Ici l'erreur est que nous utilisons que $u_{n-1}=3\times 2^{n-1} - 3^{n-1}$ en invoquant $P_n$ pour $n=0$ [premier pas de l'hérédité]. Cependant $P_n$ ne donne pas d'information sur $u_{-1}$...