# 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:

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?

• Generating functions. Flexible, applicable most everywhere. – vonbrand Jan 11 '16 at 22:44

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

• "try $an+b$ and you see that $−n−2$ fits the bill" Can you elaborate on what you mean by this? I was with you up until this part. How do you separate the homogeneous from the non-homogeneous correctly? They appear to be intertwined so I am unsure how to separate. – AJJ Jan 11 '16 at 23:08
• Do you have any recommended resources for solving non-homogeneous recurrences? I'd like to learn how to do them without needing to guess or eyeball anything; something systematic I can use until it becomes intuitive enough so I can eyeball them – AJJ Jan 12 '16 at 14:45
• It's just like constant-coefficient linear differential equations. If the non-homogeneous term is a polynomial of degree $n$, and $1$ is not a solution of the homogeneous equation, try a polynomial of degree $n$. If $x^0, \ldots, x^k$ are solutions of the homogeneous equation but $x^{k+1}$ is not, try $x^{k+1}$ times a polynomial of degree $n$. If the homogeneous term is $c^n$ times a polynomial of degree $n$, where $c$ is a constant, do the same with $c^n$ times a polynomial... Trig functions can be expressed using complex exponentials. – Robert Israel Jan 12 '16 at 16:14
• I am not really sure I understand. Why does $1$ not have to be a solution of the homogeneous equation? What does that mean, technically? – AJJ Jan 12 '16 at 16:17
• Let's say your trial solution is a polynomial $a_d n^d + \ldots + a_0$ of degree $d$, Ordinarily, when you put that in to the equation you get another polynomial of degree $d$, and you end up solving $d+1$ equations in $d+1$ unknowns for the coefficients $a_0,\ldots, a_d$, as I did with $d=1$ in the example. But if the constant $1$ is a solution of the homogeneous equation, you get a polynomial of lower degree, and the coefficient of $1$ doesn't appear at all. – Robert Israel Jan 12 '16 at 16:35

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}

• This was one of my approaches too but I had a big slowdown once I encountered the cubic equation. I didn't know how to factor it quickly. – AJJ Jan 12 '16 at 0:19
• That's what computer algebra is for.. – vonbrand Jan 12 '16 at 0:24
• Is there a way to do it without the computer algebra? I can use computers to solve the original recurrence if I wanted to, but I still want to learn to do these by hand, too. – AJJ Jan 12 '16 at 0:38
• @ArukaJ one of the factors of the denominator is clear from the left hand side (don't multiply out, like maxima does) – vonbrand Jan 12 '16 at 0:44

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

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.