4
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mastrel Jul 10 '14 at 17:33
  • $\begingroup$ 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. $\endgroup$ – Ben Grossmann Jul 10 '14 at 18:04
  • $\begingroup$ 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. $\endgroup$ – Ben Grossmann Jul 10 '14 at 18:07

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.