Relación de recurrencia $T_n=\sum_{r=0}^{n-1} T_r+2^n$

Question

De un reciente solución que publiqué aquí, trabajar desde un camino alternativo habría llevado a la siguiente relación de recurrencia que implica un término de suma:

$$T_n=\sum_{r=0}^{n-1}T_r+2^n; \qquad T_0=1\qquad (n>1)$$ ¿Cómo se puede resolver esto?

Edición 3 (sustituye a las ediciones anteriores) La condición inicial es $T_0=1$ . Para el problema tal y como está planteado, $T_1=3$ (no $4$ ) y no es necesario especificarlo como condición inicial. Esto es realmente diferente del problema anterior, que habría dado lugar a $T_n=\sum_{r=0}^{n-1}+2^{n+1}-1$ .

---

Para aclarar

Para el anterior problema al que me refería aquí La relación de recurrencia, los dos primeros términos y la forma cerrada de la solución son los siguientes: $$T_n=2T_{n-1}+\color{blue}{2^n}\\ T_n=\sum_{r=0}^{n-1}T_r+\color{blue}{2^{n+1}-1}\\ T_0=1, T_1=\color{blue}4\\ T_n=(\color{blue}n+1)2^n$$

Para el presente problema tal y como se ha publicado aquí, las relaciones de recurrencia, los dos primeros términos y la solución de forma cerrada son los siguientes: $$T_n=2T_{n-1}+\color{red}{2^{n-1}}\\ T_n=\sum_{r=0}^{n-1}T_r+\color{red}{2^n}\\ T_0=1, T_1=\color{red}3\\ T_n=(\color{red}{\frac n2}+1)2^n$$

Answer 1

Poner $S_n=\sum_1^n T_r$ . Entonces $T_n=S_n-S_{n-1}=S_{n-1}+2^n$ . Una solución particular de la recurrencia para $S_n$ es $n2^n$ . La solución general es $S_n=n2^n+a2^n$ , $a $ una constante. Es fácil de terminar.

Answer 2

Tenemos $$T_{n+1}-T_{n}=\left(\sum_{r=0}^{n}T_r+2^{n+1}\right)-\left(\sum_{r=0}^{n-1}T_r+2^n\right)=T_n+2^{n+1}-2^n,$$ es decir $$T_{n+1}=2T_n+2^n$$ para $n\ge 2$ . Dividiendo ambos lados por $2^{n+1}$ da $$\frac{T_{n+1}}{2^{n+1}}=\frac{T_n}{2^n}+\frac 12,$$ es decir $$U_{n+1}=U_n+\frac 12\quad\quad (n\ge 2)$$ donde $U_n=\frac{T_n}{2^n}$ que debería ser fácil de tratar.

Answer 3

Utilizar funciones generadoras. Definir $T(z) = \sum_{n \ge 0} T_n z^n$ , ajustar los índices en la recurrencia:

$\begin{align} T_{n + 1} = \sum_{0 \le r \le n} T_r + 2 \cdot 2^r \end{align}$

Multiplicar por $z^n$ y sumar sobre $n \ge 0$ , reconocer algunas sumas en el resultado:

$\begin{align} \frac{T(z) - T_0}{z} = \frac{T(z)}{1 - z} + \frac{2}{1 - 2 z} \end{align}$

Enchufar $T_0 = 1$ , resuelve para $T(z)$ como fracciones parciales:

$\begin{align} T(z) &= \frac{1 - z}{1 - 4 z + 4 z^2} \\ &= \frac{1 - z}{(1 - 2 z)^2} \\ &= \frac{1}{2 (1 - 2 z)^2} + \frac{1}{2 (1 - 2 z)} \end{align}$

Utilizando el teorema del binomio y una serie geométrica:

$\begin{align} T_n &= \frac{1}{2} \cdot (-1)^n \binom{-2}{n} \cdot 2^n + \frac{1}{2} \cdot 2^n \\ &= \frac{1}{2} \binom{n + 2 - 1}{2 - 1} \cdot 2^n + \frac{1}{2} \cdot 2^n \\ &= (n + 2) \cdot 2^{n - 1} \end{align}$