Quick way to get closed form for this recurrence? Is there supposed to be a fast way to compute recurrences like these?
$T(1) = 1$
$T(n) = 2T(n - 1) + n$
The solution is $T(n) = 2^{n+1} - n - 2$. 
I can solve it with:


*

*Generating functions.

*Subtracting successive terms until it becomes a pure linear recurrence $T(n) = 4T(n-1) - 5T(n-2) + 2T(n-3)$ and then solving it using the powers-of-roots approach. 

*Repeated substitution, which gives a few simple closed-forms but one messy sum $\sum_{k=1}^{n-2} 2^k k$ which to me is not easy to do quickly.
Each one of these approaches takes me several minutes to flesh out, but I feel like this is supposed to be one of those questions I should be able to answer in a few seconds and move on. What am I missing? Is there some quick trick to doing these recurrences?

Generating functions. Define $t(z) = \sum_{n \ge 0} T(n) z^n$, shift indices to $T(n + 1) = 2 T(n) + n + 1$; by the recurrence backwards $T(0) = 0$, and you get directly:
$\begin{align}
  \frac{t(z) - T(0)}{z}
    &= 2 t(z) + \sum_{n \ge 0} (n + 1) z^n \\
    &= 2 t(z) + \frac{1}{(1 - z)^2} \\
  t(z)
    &= \frac{z}{1 - 4 z + 5 z^2 - 2 z^3} \\
    &= \frac{2}{1 - 2 z} - \frac{1}{1 - z} - \frac{1}{(1 - z)^2}
\end{align}$
You can read off the terms from the partial fraction expansion:
$\begin{align}
   T(n)
     &= 2 \cdot 2^n - 1 - (n + 1) \\
     &= 2^{n + 1} - n - 2
\end{align}$
