# Going from closed form to recurrence relation

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?

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$$
• 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. – Ben Grossmann 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. – Ben Grossmann Jul 10 '14 at 18:07