<s>[INST] Solve the following recurrence relation: $S(1) = 2$; $S(n) = 2S(n-1)+n2^n, n \ge 2$ Solve the following recurrence relation:
$$\begin{align}
S(1) &= 2 \\
S(n) &= 2S(n-1) + n 2^n, n \ge 2
\end{align}$$

I tried expanding the relation, but could not figure out what the closed relation is:

+-------+------------------------------------------------+
|   n   |  S(n)                                          |
+-------+------------------------------------------------+
|   1   |  2                                             |
|   2   |  2S(1)+2*2^2 = 2*2 + 2*2^2 = 2^2 + 2*2^2 =     |
|       |              = 4 + 8 = 12                      |
|   3   |  2S(2)+3*2^3 = 2*(2^2 + 2*2^2) + 3*2^3 =       |
|       |              = 8 + 16 + 24 = 48                |
|   4   |  2S(3)+4*2^4 = 2*(2*2^2 + 2*2*2^2 + 3*2^3) +   |
|       |              + 4*2^4 =                         |
|       |              = 16 + 32 + 48 + 64 = 160         |
|   5   |  2S(4)+5*2^5 = 2*(2*2*2^2 + 2*2*2*2^2 +        |
|       |              + 2*3*2^3 + 4*2^4) + 5*2^5 =      |
|       |              = 32 + 64 + 96 + 128 + 160        |
|       |              = 384 + 96 = 480                  |
+-------+------------------------------------------------+


Edit: is it $S(n)=2^n\frac{n(n+1)}{2}$?

 [/INST] We can write $S(n)=2+2(2^2)+3(2^3)+\cdots+n(2^n)$.  However, we can simplify the problem slightly by generalizing: replace $2$ with $x$ to get 
$$f_n(x)=x+2x^2+3x^3+\cdots+ nx^n = x(1+2x+3x^2+\cdots+nx^{n-1})=x \frac{d}{dx}(1+x+\cdots+x^n)$$
Now, using the formula for a geometric sum, $1+x+\cdots+x^n=\frac{1-x^{n+1}}{1-x}$, and differentiating we have
$$f_n(x)=x \frac{d}{dx}\left(\frac{1-x^{n+1}}{1-x}\right)=x\frac{(1-x)(-(n+1)x^{n})+(1-x^{n+1})}{(1-x)^2}$$
Plugging back in with $x=2$, we have $$S(n)=f_n(2)=2((n+1)2^n+1-2^{n+1})=2((n-1)2^n+1)=(n-1)2^{n+1}+2.$$

I believe there was a typo in the problem, I solved $S(1)=2;S(n)=S(n-1)+n2^n$, which was the formula in the problem but not in the title.  What follows is a solution the the recurrence in the title.
Let $T(n)=S(n)/2^n$.  Then dividing the formula $S(n)=2S(n-1)+n2^n$ by $2^n$, we get
$$T(n)=T(n-1)+n,\qquad T(1)=1.$$ 
Plugging in and using the standard formula for triangular number, $T(n)=1+2+3+\cdots+n=\frac{n(n+1)}{2}$.  Thus, $S(n)=n(n+1)2^{n-1}$
</s>