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?
 A: Just as in linear algebra, the general solution of a linear non-homogeneous equation is a particular solution + the general solution of the homogeneous equation.
The homogeneous equation $T(n) = 2 T(n-1)$ has the obvious solutions $c 2^n$.
For a particular solution of the non-homogeneous equation $T(n) = 2 T(n-1) + n$, since the non-homogeneous term is a polynomial of degree $1$ it's  natural to look for a solution that is again a polynomial of degree $1$: try $a n + b$ and you see that $-n - 2$ fits the bill.  
EDIT: What I mean is that substituting $T(n) = a n + b$ gives you 
$a n + b  = 2 (a (n-1) + b) + n$, which simplifies to $(a + 1) n + b - 2 a = 0$, and since this is true for all $n$ you must have $a+1 = 0$, $b-2a = 0$, i.e. $a=-1$ and $b = -2$.
So your general solution is $T(n) = c 2^n - n - 2$, and you plug in the initial condition $n = 1$ to see that $c = 2$. 
A: 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}$
A: Let me make the problem slightly more complex with, for example, $$T_n=a \, T_{n-1}+b+c n+d n^2$$ ($a,b,c,d$ being given); set $$T_n=U_n+\alpha +\beta  n+\gamma  n^2$$ Now, replace in the original expression
$$U_n+\alpha+\beta  n +\gamma  n^2=a\left(U_{n-1}+\alpha +\beta  (n-1)+\gamma  (n-1)^2\right)+b+c n+d n^2$$ that is to say $$U_n-aU_{n-1}=a\left(\alpha +\beta  (n-1)+\gamma  (n-1)^2\right)+b+c n+d n^2-(\alpha+\beta  n +\gamma  n^2)$$ Expanding the rhs and grouping for a given power of $n$ then gives
$$(a \alpha -a \beta +a \gamma -\alpha +b)+n (a \beta -2 a \gamma -\beta +c)+n^2 (a
   \gamma -\gamma +d)$$ Say that, for any $n$, this expression is equal to $0$. This gives three linear equations for three unknowns $\alpha,\beta,\gamma$; these are easy to solve and you then finish with the simplest reccurence equation $$U_n=a\,U_{n-1}$$ Then, back to $T_n$.
For sure, you can generalized the problem to any recurrence of the form $$T_n=a \, T_{n-1}+\sum_{i=0}^k c_in^i$$
A: Solve the homogeneous equation by removing any non-functional terms. In this case, simply remove the n.
Solve the specific solution by guessing. In this case, it's not difficult. Try plugging in Ax + b into the functional equation, and see if you can solve for the coefficients.
Then, add both solutions together for the general solution.
