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

\begin{align} T(n) & = 2 T(n-1) + n = 2(2T(n-2) + n-1) + n = 4T(n-2) + 2(n-1) + n\\ & = 8 T(n-3) + 4(n-2) + 2(n-1) + n = 2^k T(n-k) + \sum_{j=0}^{k-1} 2^j (n-j)\\ & = 2^{n-1} T(1) + \sum_{j=0}^{n-2}2^j (n-j) = 2^{n-1} + \sum_{j=0}^{n-2}2^j (n-j) \end{align} \begin{align} \sum_{j=0}^{n-2}2^j (n-j) & = n \sum_{j=0}^{n-2}2^j - \sum_{j=0}^{n-2} j2^j = n(2^{n-1}-1) - \dfrac{n \cdot 2^n - 3 \cdot 2^n + 4}2\\ & = n(2^{n-1}-1) - (n \cdot 2^{n-1} -3 \cdot 2^{n-1} + 2) = 3 \cdot 2^{n-1} -n - 2 \end{align} Por lo tanto, $$T(n) = 2^{n-1} + 3 \cdot 2^{n-1} -n - 2 = 2^{n+1} - n - 2$$

EDITAR (Añadir detalles)

En primer lugar, hay que tener en cuenta que $\displaystyle \sum_{j=0}^{n-2}2^j$ es la suma de una progresión geométrica y se puede sumar como se muestra a continuación. $$\sum_{j=0}^{k} x^j = \dfrac{x^{k+1} -1}{x-1}$$ $\displaystyle \sum_{j=0}^{n-2} j2^j$ es una suma de la forma $\displaystyle \sum_{j=0}^{k} jx^j$ $$\sum_{j=0}^{k} jx^j = x \sum_{j=0}^{k} jx^{j-1} = x \dfrac{d}{dx} \left( \sum_{j=0}^k x^j\right) = x \dfrac{d}{dx} \left( \dfrac{x^{k+1} - 1}{x-1}\right) = x \left( \dfrac{kx^{k+1} - (k+1) x^k +1}{(x-1)^2} \right)$$

Answer 2

Una pista: sustituto $T(n)=G(n)-n-2$

Answer 3

Inducción: Para $n=1$ , $T(1)=1=2^{1+1}-1-2$ . Supongamos que $T(n-1)=2^n-n+1-2=2^n-n-1$ . Entonces $T(n)=2T(n-1)+n=2^{n+1}-2n-2+n=2^{n+1}-n-2$ lo que completa la prueba.

Answer 4

Utilicemos el método de aniquilación para convertir esto en una recurrencia homogénea de tercer orden, y luego resolver con una ecuación característica. Primero, escribimos la recurrencia así $n$ es el menor índice: $$T(n) - 2T(n-1)= n \implies T(n+1)-2T(n) = n+1$$

Entonces, reescribimos la recurrencia en términos del operador de desplazamiento $E$ : $$(E-2)T(n) = n+1$$

La aplicación de la $(E-1)$ a ambos lados de la ecuación, tenemos: $$(E-1)^2(E-2)T(n) = (E-1)^2(n+1)$$

Ahora bien, como $(E-1)^2(n+1) = 0$ (aniquila ese término), tenemos: $$(E-1)^2(E-2)T(n) = 0$$

La ecuación característica es, entonces $(r-1)^2(r-2)=0$ Así que nuestras raíces son $r=1$ (con multiplicidad $2$ ) y $r=2$ . Entonces, la recurrencia tiene la forma: \begin{align*} T(n) &= c_1\cdot 2^n + c_2 \cdot n1^n + c_3 \cdot 1^n\\ &= c_1\cdot 2^n + nc_2 + c_3 \end{align*}

Utilizando la relación de recurrencia, calculamos $T(1) = 1, T(2) = 4, T(3) = 11$ y ahora puede resolver para $(c_1, c_2, c_3)$ que da la solución $(2, -1, -2)$ .

Answer 5

Esta recurrencia $$T(n) = 2T(n-1) + n$$ es difícil porque contiene $n$ . Sea $D(n) = T(n) - T(n-1)$ y calcular $D(n+1) = 2D(n) + 1$ esta recurrencia no es tan difícil. Por supuesto $D(1) = 4 - 1 = 2 + 1$ .

La secuencia $D(n)$ va: $2 + 1$ , $2^2 + 2 + 1$ , $2^3 + 2^2 + 2 + 1$ . $D(n) = 2^{n+1}-1$ .

Ahora $$T(n) = \sum_{i=1}^n D(i) = 2 \sum_{i=1}^n 2^{i} - \sum_{i=1}^n 1 = 2^{n+1}-2-n.$$