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

If I had a closed form for a sequence that I suspect to represents a recurrence relation how would I determine the recurrence relation?

In particular, I have the sequence

$$a_n = \frac{1}{4}\bigg(\frac{3}{2}+\sqrt{2}\bigg)^n + \frac{1}{4}\bigg(\frac{3}{2}-\sqrt{2}\bigg)^n$$

This reminds me of the closed form for the Fibonacci sequence, so I would assume that the sequence would satisfy a recurrence relation of the form $a_n = ba_{n-1}+ca_{n-2}$ for some integers (or at least rationals) $b,c$. What is a method I could use to determine the recurrence relation or determine that no recurrence relation exists?

share|cite|improve this question
up vote 7 down vote accepted

Suppose we want to find a recurrence relation such that $a_n = \left(\frac{3}{2}+\sqrt{2}\right)^n$ and $a_n = \left(\frac{3}{2}-\sqrt{2}\right)^n$ are both solutions, which has the form $$ a_n -b a_{n-1} -c a_{n-2} = 0 $$ If we assume that $a_n = r^n$ for some $r$ is a solution, we'd have $$ r^2(a_{n-2}) - br(a_{n-2}) + ca_{n-2} = 0 \implies\\ r^2 - br - c = 0 $$ So, it suffices to find $b,c$ such that $r = \frac{3}{2} \pm \sqrt{2}$ are the roots of the equation $r^2 - br - c = 0$. The unique choice that works is $$ b = 3\\ c = -1/4 $$ So, your sequence will be the unique solution to the recurrence problem $$ a_n = 3a_{n-1} - \frac 14 a_{n-2}\\ a_0 = \frac 12, \quad a_1 = \frac 34 $$

share|cite|improve this answer
I see that this is the correct answer but why do you start with trying to find a recurrence relation such that $a_n = \bigg(\frac{3}{2} \pm \sqrt{2}\bigg)^n$ instead of one quarter of the sum of them as was the question? – Mastrel Jul 10 '14 at 17:33
Note that if $a_n$ and $a_n'$ are solutions to the recurrence $a_n = b a_{n-1} + ca_{n-2}$, then so is any combination $c_1 a_n + c_2 a_n'$. The form $a_n = r^n$ is simply an Ansatz. – Omnomnomnom Jul 10 '14 at 18:04
So by the above, it's clear that my method makes sense. The practical reason to do things this way is that $a_n = r^n$ is a much easier solution to work with directly. – Omnomnomnom Jul 10 '14 at 18:07

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.