\( 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 = 16 \cdot 1 + 8 \cdot 1 + 4 \cdot 3 + 2 \cdot 9 + 1 \cdot 27 = 16 + 8 + 12 + 18 + 27 = 81. \] En résumé, nous avons 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 peut observer que les termes semblent suivre la forme \( u_n = 3^n \) pour \( n \geq 1 \). Pour prouver cela par récurrence, nous allons supposer que \( u_n = 3^n \) pour tout \( n \) jusqu'à \( k \) et montrer que cela est vrai pour \( k+1 \). **Hypothèse de récurrence** : Supposons que \( u_i = 3^i \) pour \( i = 0, 1, \ldots, k \). **À prouver** : \( u_{k+1} = 3^{k+1} \). Calculons \( u_{k+1} \) : \[ u_{k+1} = \sum_{i=0}^{k} 2^{k-i} u_i = \sum_{i=0}^{k} 2^{k-i} 3^i. \] Cette somme est une somme géométrique : \[ u_{k+1} = 2^k \sum_{i=0}^{k} \left( \frac{3}{2} \right)^i = 2^k \cdot \frac{1 - \left( \frac{3}{2} \right)^{k+