Solve the following recurrence relation: $S(1) = 2$; $S(n) = 2S(n-1)+n2^n, n \ge 2$

Question

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}$?

Answer 1

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}$

Answer 2

Given $$ S(n)=2S(n-1)+n2^n\tag{1} $$ Consider $T(n)=2^{-n}S(n)$. $T(1)=1$ and, multiplying $(1)$ by $2^{-n}$, we have the recurrence $$ T(n)=T(n-1)+n\tag{2} $$ Therefore, $T(n)=\frac{n^2+n}2$ and thus, $$ S(n)=(n^2+n)\,2^{n-1}\tag{3} $$