2
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Generating functions. Flexible, applicable most everywhere. $\endgroup$ – vonbrand Jan 11 '16 at 22:44
6
$\begingroup$

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

$\endgroup$
12
  • $\begingroup$ "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. $\endgroup$ – AJJ Jan 11 '16 at 23:08
  • $\begingroup$ 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 $\endgroup$ – AJJ Jan 12 '16 at 14:45
  • $\begingroup$ 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. $\endgroup$ – Robert Israel Jan 12 '16 at 16:14
  • $\begingroup$ 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? $\endgroup$ – AJJ Jan 12 '16 at 16:17
  • $\begingroup$ 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. $\endgroup$ – Robert Israel Jan 12 '16 at 16:35
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – AJJ Jan 12 '16 at 0:19
  • $\begingroup$ That's what computer algebra is for.. $\endgroup$ – vonbrand Jan 12 '16 at 0:24
  • $\begingroup$ 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. $\endgroup$ – AJJ Jan 12 '16 at 0:38
  • 1
    $\begingroup$ @ArukaJ one of the factors of the denominator is clear from the left hand side (don't multiply out, like maxima does) $\endgroup$ – vonbrand Jan 12 '16 at 0:44
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.