Resolver la recurrencia $T(n) = 2T(n-1) + n$

Question

Resolver la recurrencia $T(n) = 2T(n-1) + n$ donde $T(1) = 1$ y $n\ge 2$ .

La respuesta final es $2^{n+1}-n-2$

¿Puede alguien llegar a la solución?

Answer 1

Algunas de las soluciones presentadas aquí son muy arcanas. Basándonos en la pista dada por @Norbert, consideramos el problema generalizado

$${{T}_{n}}=A{{T}_{n-1}}+Bn,\quad{{T}_{1}}\,\,\,\text{specified}$$

Dejemos que $ {{T}_{n}}={{f}_{n}}+pn+q$ para que

$${{f}_{n}}=A{{f}_{n-1}}+n\left[Ap+B-p \right]+\left[ -Ap+Aq-q \right] $$

A continuación, elija $p$ y $q$ para eliminar las cantidades entre paréntesis, es decir

$$p=-\frac{B}{A-1};\quad q=-\frac{AB}{{{\left( A-1 \right)}^{2}}} \\ {{f}_{n}}=A{{f}_{n-1}} \\ $$

Ahora, para que $p$ y $q$ y, por tanto, que la secuencia sea de números enteros, debe ser que $A=2$ . Claramente, la solución para $f$ es $f_n=2^{n-1}f_1$ y la solución general viene dada por

$$ \begin{align} T &=(T_1-p-q)2^{n-1}+pn+q\\ &=(T_1+3B)2^{n-1}-B(n+2) \end{align} $$

Este resultado está de acuerdo con los otros presentados aquí y ha sido probado numéricamente contra la fórmula de recurrencia para valores enteros positivos y negativos arbitrarios de $T_1$ y $B$ .

Answer 2

Por sustracción $$ \begin{array}{rrcl} & T(n)-2T(n-1) &=& n \\ & T(n-1) - 2T(n-2) &=& n-1 \\ \hline & T(n)-3T(n-1)+2T(n-2) &=& 1 \end{array}$$

De nuevo, por sustracción

$$ \begin{array}{rrcl} & T(n)-3T(n-1)+2T(n-2) &=& 1 \\ & T(n-1)-3T(n-2)+ 2T(n-3) &=& 1 \\ \hline & T(n)-4T(n-1)+5T(n-2)-2T(n-3) &=& 0 \end{array}$$

La ecuación característica de la recursión es

$$x^3-4x^2+5x-2 = 0$$

Las raíces de la ecuación son $x_1 = x_2 = 1$ y $x_3 = 2$

Así, la solución general de la recursión es $$T(n) = C_1\cdot 1^n + C_2\cdot n\cdot 1^n + C_3\cdot 2^n$$ o $$T(n) = C_1 + C_2\cdot n + C_3\cdot 2^n$$

ahora, desde $T(1) = 1$ obtenemos $T(2) = 4$ y $T(3) = 11$ .

Así, obtenemos el sistema

$$ \begin{array}{ccccccc} C_1 &+&C_2 &+& 2C_3 &=& 1 \\ C_1 &+&2C_2&+&4C_3 & =& 4 \\ C_1 & +& 3C_2 &+& 8C_3 &=& 11 \end{array}$$

De este sistema obtenemos que $C_1 = -2$ , $C_2 =-1$ y $C_3 = 2$ por lo que la solución particular de la recursión es $$T(n) =2\cdot2^n-n-2,$$ o $$T(n) = 2^{n+1}-n-2.$$

Answer 3

T(n)=2T(n-1)+n -----(1)
T(n-1)=2T(n-2)+n-1 ------(2)
T(n-2)=2T(n-3)+n-2 ------(3)

Sustituye (3) en (2) y luego (2) en (1)

T(n-1)= $2^2T$ (n-3)+2(n-2)+(n-1)

T(n)= $2^3$ T(N-3)+ $2^2$ (n-2)+2(n-1)+n

\=> T(k)= $2^k$ T(n-k) + $2^{k-1}$ (n-(k-1))+........+ $2^0$ n

Ahora, como T(1)=1, dejemos n-k=1 => k=n-1

T(n)= $2^{n-1}$ T(1) + $2^{n-2}$ (2) + $2^{n-3}$ (3) + $2^{n-n}$ (n) --------(4)

Multiplica la ecuación (4) por 2

T(n)= $2^{n}$ + $2^{n-1}$ + $2^{n-2}$ + $2^{n-3}$ +...... + 2n ----------- (5)

Resta la ecuación (5) con (4)

T(n)= $2^{n}$ + $2^{n-1}$ + $2^{n-2}$ + $2^{n-3}$ +........+2 -n

Usando la suma de los términos de GP, obtenemos :

[ $2^{1}$ ( $2^{n}$ -1) - n ]/ (2-1)

\= $2^{n+1}$ -2 -n

Answer 4

Aquí hay un enfoque de función generadora para derivar y demostrar la fórmula deseada. Escribe $T(n)$ como $T_n$ y que $f(z) = \sum_{n=1}^\infty T_n z^n$ sea la función generadora ordinaria. Ahora, utilice la relación de recurrencia y la condición inicial para obtener $$T_1 z^1 + \sum_{n=2}^\infty (T_n-2T_{n-1}) z^n = z + \sum_{n=2}^\infty n z^n,$$ de manera equivalente, $$f(z)-2z f(z)=z + \left(z\sum_{n=1}^\infty n z^{n-1} - z\right) = z D_z \left(\sum_{n=1}^\infty z^n\right)=z D_z\left(\frac{1}{1-z}\right)=\frac{z}{(1-z)^2}.$$ Resolver para $f(z)$ rinde $$f(z) = \frac{z}{(1-2z)(1-z)^2}.$$ Ahora utilice la descomposición parcial de la fracción para obtener $$ f(z) = \frac{2}{1-2z}-\frac{1}{1-z}-\frac{1}{(1-z)^2} = \sum_{n=0}^\infty \left(2 \cdot 2^n - 1 - (n+1)\right)z^n, $$ lo que implica que $$T_n = 2 \cdot 2^n - 1 - (n+1) = 2^{n+1} - n - 2.$$