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