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érifions 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$ quelconque (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, on obtient :

   $ 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 pour tout entier naturel $n$.
   Par conséquent, d'après le principe de récurrence, pour tout $n \in \mathbb{N}$ :

   $ u_n=2^n+n $