$T(n)=2T(n-1)+n,T(1)=1,n\ge2$ 
Solve the recurrence $T(n)=2T(n-1)+n,T(1)=1,n\ge2$

My approach:
$$T(n)=2T(n-1)+n$$
$$T(n)=2(2T(n-2)+(n-1))+n$$
$$T(n)=4T(n-2)+2(n-1)+n\dots$$
$$T(n)=2^kT(n-k)+2^{k-1}(n-k+1)+\dots+2^{k-k}n$$
From initial conditions, $k=n-1$:
$$T(n)=2^{n-1}1+2^{n-2}2+\cdot\cdot\cdot\cdot+2^{n-n}n$$
Now what?
 A: $$f(x)=x2^{n-1}+x^22^{n-2}+...+x^n=2^n\left(\frac{x}{2}+\left(\frac{x}{2}\right)^2+...+\left(\frac{x}{2}\right)^n\right)=$$
$$=2^n\cdot\frac{\frac{x}{2}\left(\left(\frac{x}{2}\right)^n-1\right)}{\frac{x}{2}-1}=\frac{x^{n+1}-x2^n}{x-2}.$$
Now, calculate $f'(1).$
I got $$1\cdot2^{n-1}+2\cdot2^{n-2}+...+n\cdot2^0=f'(1)=2^{n+1}-n-2.$$
A: Probably one of the best approaches to attack this kind of recurrence is through generating functions.
Define
$$S(x):=\sum_{n\ge1}T(n)x^n,$$
then we have
\begin{align}
S(x) =&\ x+\sum_{n\ge2}(2T(n-1)+n)x^n\\
=&\ 2xS(x) + \sum_{n\ge1}nx^n\\
=&\ 2xS(x)+x\frac{d}{dx}\sum_{n\ge0}x^n\\
=&\ 2xS(x)+x\frac{d}{dx}\frac{1}{1-x}\ .
\end{align}
It follows that
$$S(x) = \frac{x}{(1-2x)(1-x)^2}\ .$$
Now find the (formal) Taylor expansion of the right hand side to get your solution.
A: You can see that if $T(n)=2\cdot T(n-1)+n$ and $T(1)=1$ then you'll have a sequence of $T(1),T(2),T(3),T(4),T(5),\dots$ that looks like this:
$1,4,11,26,57,120,\dots$ and so on. From this you can see that $T(n)= 2^{n+1} - n - 2$
