<s>[INST] Solve the recurrence $T(n) = 2T(n-1) + n$ Solve the recurrence  $T(n) = 2T(n-1) + n$
where $T(1) = 1$ and $n\ge 2$.
The final answer is $2^{n+1}-n-2$
Can anyone arrive at the solution?
 [/INST] Here's a generating-function approach to both derive and prove the desired formula.
Write $T(n)$ as $T_n$, and let $f(z) = \sum_{n=1}^\infty T_n z^n$ be the ordinary generating function. Now use the recurrence relation and initial condition to obtain
$$T_1 z^1 + \sum_{n=2}^\infty (T_n-2T_{n-1}) z^n = z + \sum_{n=2}^\infty n z^n,$$
equivalently,
$$f(z)-2z f(z)=z + \left(z\sum_{n=1}^\infty n z^{n-1} - z\right) = z D_z \left(\sum_{n=1}^\infty z^n\right)=z D_z\left(\frac{1}{1-z}\right)=\frac{z}{(1-z)^2}.$$
Solving for $f(z)$ yields
$$f(z) = \frac{z}{(1-2z)(1-z)^2}.$$
Now use partial fraction decomposition to obtain
$$
f(z) = \frac{2}{1-2z}-\frac{1}{1-z}-\frac{1}{(1-z)^2}
= \sum_{n=0}^\infty \left(2 \cdot 2^n - 1 - (n+1)\right)z^n,
$$
which implies that
$$T_n = 2 \cdot 2^n - 1 - (n+1) = 2^{n+1} - n - 2.$$
</s>