Démonstration par récurrence

Démontrons par récurrence que pour tout entier naturel $n$, on a la propriété $\mathcal{P}(n)$ : « $u_n = 2^n+n$ ».

1. Initialisation :
   Vérifier si la propriété est vraie pour $n=0$.

   • D'une part, d'après l'énoncé, $u_0 = 1$.
   • D'autre part, pour $n=0$, on a $2^0+0 = 1+0 = 1$.

   La propriété est donc vraie pour $n=0$.

2. Hérédité :
   Supposons que la propriété soit vraie pour un certain entier naturel $n$ (hypothèse de récurrence), c'est-à-dire :

   $u_n=2^n+n$

   Montrons qu'elle est alors vraie pour l'entier suivant $n+1$, c'est-à-dire que $u_{n+1} = 2^{n+1} + (n+1)$.

   D'après la relation de récurrence de l'énoncé :
   $u_{n+1} = 2u_n - n + 1$
   En remplaçant $u_n$ par l'expression supposée dans l'hypothèse de récurrence :
   $u_{n+1} = 2(2^n + n) - n + 1$
   En développant et en simplifiant :
   $u_{n+1} = 2 \times 2^{n} + 2n - n + 1$
   $u_{n+1} = 2^{n+1} + n + 1$
   La propriété est donc héréditaire.

3. Conclusion :
   La propriété est vraie pour $n=0$ et elle est héréditaire. Par conséquent, d'après le principe de récurrence, pour tout $n \in \mathbb{N}$ :

   $\mathbf{u_n=2^n+n}$