Quick way to get closed form for this recurrence?

Question

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:

1. Generating functions.

2. 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.

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

Answer 1

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

Answer 2

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}$

Answer 3

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.

Answer 4

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