\( u_{0}=1 \) et pour tout \( n \geq 0, u_{n+1}=\sum_{i=0}^{n} 2^{n-i} u_{i} \)

La suite \( (u_n) \) est définie par \( u_0 = 1 \) et pour tout \( n \geq 0 \), par la relation de récurrence : \[ u_{n+1} = \sum_{i=0}^{n} 2^{n-i} u_i. \] Pour mieux comprendre cette suite, calculons quelques termes : 1. **Pour \( n = 0 \)** : \[ u_1 = \sum_{i=0}^{0} 2^{0-i} u_i = 2^{0-0} u_0 = 1 \cdot 1 = 1. \] 2. **Pour \( n = 1 \)** : \[ u_2 = \sum_{i=0}^{1} 2^{1-i} u_i = 2^{1-0} u_0 + 2^{1-1} u_1 = 2^1 \cdot 1 + 2^0 \cdot 1 = 2 + 1 = 3. \] 3. **Pour \( n = 2 \)** : \[ u_3 = \sum_{i=0}^{2} 2^{2-i} u_i = 2^{2-0} u_0 + 2^{2-1} u_1 + 2^{2-2} u_2 = 2^2 \cdot 1 + 2^1 \cdot 1 + 2^0 \cdot 3 = 4 + 2 + 3 = 9. \] 4. **Pour \( n = 3 \)** : \[ u_4 = \sum_{i=0}^{3} 2^{3-i} u_i = 2^{3-0} u_0 + 2^{3-1} u_1 + 2^{3-2} u_2 + 2^{3-3} u_3 = 2^3 \cdot 1 + 2^2 \cdot 1 + 2^1 \cdot 3 + 2^0 \cdot 9 = 8 + 4 + 6 + 9 = 27. \] 5. **Pour \( n = 4 \)** : \[ u_5 = \sum_{i=0}^{4} 2^{4-i} u_i = 2^{4-0} u_0 + 2^{4-1} u_1 + 2^{4-2} u_2 + 2^{4-3} u_3 + 2^{4-4} u_4 = 2^4 \cdot 1 + 2^3 \cdot 1 + 2^2 \cdot 3 + 2^1 \cdot 9 + 2^0 \cdot 27. \] Calculons cela : \[ = 16 + 8 + 12 + 18 + 27 = 81. \] Nous avons donc calculé les premiers termes de la suite : - \( u_0 = 1 \) - \( u_1 = 1 \) - \( u_2 = 3 \) - \( u_3 = 9 \) - \( u_4 = 27 \) - \( u_5 = 81 \) On remarque que les termes semblent suivre la forme \( u_n = 3^n \) pour \( n \geq 1 \). Vérifions si cette conjecture est vraie par récurrence. **Base de récurrence** : Pour \( n = 1 \), \( u_1 = 3^1 = 3 \) (vrai). **Hypothèse de récurrence** : Supposons que \( u_k = 3^k \) pour tout \( k \leq n \). **Étape de récurrence** : Montrons que cela implique \( u_{n+1} = 3^{n+1} \). \[ u_{n+1} = \sum_{i=0}^{n} 2^{n-i} u_i = 2^n u_0 + 2^{n-1} u_1 + 2^{n-2} u_2 + \ldots + 2^0 u_n. \] En utilisant l'hypothèse de récurrence : \[ = 2^n \cdot 1 + 2^{n-1} \cdot 1 + 2^{n-2} \