\begin{questions}
\item
Raisonnons par récurrence sur $n$.
\begin{itemize}
\item Pour $n=0$, on a : $2^n+n+1=2^0+0+1=2=u_0$.
\item Supposons la formule vraie pour un entier naturel $k$ arbitrairement fixé.
\par
On calcule :
\[
\begin{aligned}
u_{k+1} &= 2u_k-k \\
&= 2(2^k+k+1)-k \\
&= (2^{k+1}+2k+2)-k \\
&= 2^{k+1}+k+2 \\
&= 2^{k+1}+(k+1)+1.
\end{aligned}
\]
C'est bien la formule au rang $(k+1)$.  \par
On a donc prouvé par récurrence que, pour tout entier naturel $n$,\linebreak[4] $u_n~=~2^n~+~n~+~1$.
\end{itemize}
                                
\item Nous allons démontrer par récurrence l'assertion :
\[\mathcal{P}(n) :\quad \Big[\: (*)\: v_n=2^{n+1}-3^n
\quad\textrm{et}\quad(**)\:  v_{n+1}=2^{n+2}-3^{n+1}\ \Big]\]
\begin{itemize}
\item Pour $n=0$, on a $\,2^{n+1}-3^n=2-1=1=v_0$ d'où $(*)$.
\par
Enfin,  $\,2^{n+2}-3^{n+1}=4-3=1=v_1$ qui est $(**)$ : on a vérifié ${\cal P}(0)$.
\item Supposons l'assertion ${\cal P}(k)$ vraie pour un certain entier naturel $k$. \par
On sait déjà : $\,v_{k+1}=2^{k+2}-3^{k+1}$ (d'après l'hypothèse de récurrence), qui est la partie  $(*)$  de l'assertion  ${\cal P}(k+1)$.\\
On calcule :
\begin{align*}
v_{k+2}=5v_{k+1}-6v_k&=5(2^{k+2}-3^{k+1})-6(2^{k+1}-3^k)\\
&=5\times 2^{k+2}-5\times 3^{k+1}-6\times 2^{k+1}+6\times 3^k\\
&=5\times 2^{k+2}-5\times 3^{k+1}-3\times 2^{k+2}+2\times 3^{k+1}\\
&=2\times 2^{k+2}-3\times 3^{k+1}\\
&=2^{k+3}-3^{k+2}
\end{align*}
qui est $(**)$ au rang  $(k+1)$. On a ainsi vérifié  ${\cal P}(k+1)$.
\end{itemize}
On en déduit, d'après le principe de récurrence, que, pour tout entier naturel $n$, $v_n=2^{n+1}-3^n$.
%\begin{attention}
%La suite $v_n$ est une suite linéaire récurrente d'ordre deux (chaque terme dépend des deux termes qui le précèdent). Il est donc nécessaire de modifier l'hypothèse de récurrence. Une telle récurrence est parfois appelée récurrence double.
%\end{attention}
\end{questions}
