Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm currently stonewalled on this problem, in which I have to solve the following recurrence relation and prove my answers satisfy the recurrence.

My boundary conditions are $a_0 = 1$ and $a_1 = 9$.

The problem is $\forall\ n \in N$, $a_{n+2}-18a_{n+1}+9a_{n}=0$

I ended up with the sequence proceeding as $1, 9, 153, 2673, 46737$ for $a_{0}, a_{1}, a_{2}, a_{3},$ and $a_{4}$ respectively but I can't actually figure out the pattern that would give me a solution. Help?

share|cite|improve this question
Are you familiar with the method of solving linear recurrence relations via the characteristic polynomial? – Alex Wertheim Jun 8 '13 at 3:41
I am not. This class has been kind of rushed, to put it mildly. – Harry Tuttle Jun 8 '13 at 3:44
up vote 4 down vote accepted

There is a standard procedure for dealing with such problems. One looks for solutions of the form $r^n$.

Substituting in the recurrence, we get, if I am reading the coefficients correctly, the equation $r^{n+2}-18r^{n+1}+9r^n=0$. On the assumption $r\ne 0$, we get $r^2-18r+9=0$, which has the solutions $$r=9\pm6\sqrt{2}.$$ Let $\alpha$ and $\beta$ be these solutions of the quadratic equation. It is easy to verify that for any constants $A$ and $B$, $A\alpha^n+B\beta^n$ is a solution of the recurrence.

From the initial conditions, you can calculate what $A$ and $B$ must be. (That part is left to you.)

So for the $A$ and $B$ that you found, if we put $a_n=A\alpha^n+B\beta^n$, the recurrence and initial conditions are satisfied. But it is easy to prove by induction that there is only one solution to the recurrence with initial conditions. So we must have found it.

Remark: The method described above can be used for all linear homogeneous recurrences with constant coefficients. There is a small complication when the equation we get has roots of multiplicity greater than $1$.

share|cite|improve this answer

Many recurrences can be solved by Wilf's techniques from "generatingfunctionology". Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$ and sum over $n \ge 0$ to get: $$ \frac{A(z) - a_0 - a_1 z}{z^2} - 18 \frac{A(z) - a_0}{z} + 9 A(z) = 0 $$ Solve for $A(z)$ and split into partial fractions: $$ A(z) = \frac{1}{2} \frac{1}{1 - (9 + 3 \cdot 2^{3/2}) z} + \frac{1}{2} \frac{1}{1 - (9 - 3 \cdot 2^{3/2}) z} $$ From here, recognizing two geometric series: $$ a_n = \frac{(9 + 3 \cdot 2^{3/2})^n + (9 - 3 \cdot 2^{3/2})^n}{2} $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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