Exercices de Raisonnements, Sup (prépa) (page 2)

On va démontrer par récurrence forte sur $n\ge 1$ la propriété $\mathcal{P}(n)$ suivante : "$u_n=2^{n-1}$".

Initialisation : D'après la formule de récurrence, $u_1=u_0=1=2^{1-1}$. La propriété est donc initialisée au rang $n=1$.

Hérédité : Soit $n\ge 1$. Supposons la propriété $\mathcal{P}(k)$ démontrée pour tous les $k$ compris entre 1 et $n$ (c'est-à-dire $u_k=2^{k-1}$ pour $1\le k\le n$, et on a aussi $u_0=1$), et prouvons que $\mathcal{P}(n+1)$ est également vraie.

On a, appliquant d'abord la définition de $u_{n+1}$, puis l'hypothèse de récurrence :

$u_{n+1}=u_0+u_1+u_2+\cdots +u_n$

$=1+(1+2+2^2+\cdots +2^{n-1})$

D'après la formule donnant la somme des termes d'une suite géométrique (pour la partie entre parenthèses), on déduit que :

$u_{n+1}=1+\sum _{k=0}^{n-1}{2}^k=1+\frac{1-2^n}{1-2}=1+\frac{1-2^n}{-1}=1-(1-2^n)=2^n$

On a $2^n=2^{(n+1)-1}$. Donc la propriété $\mathcal{P}(n+1)$ est vraie.

Conclusion : Par le principe de récurrence forte, la propriété $\mathcal{P}(n)$ est vraie pour tout entier $n\ge 1$.