<s>[INST] 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?
 [/INST] 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
$$
</s>