Finding a closed form expression for the following recurrence relation.

Question

Given that:

$S_0 = 0$

$S_1 = 3$

$S_n = S_{n-1} + 6S_{n-2}$ for $n ≥ 2$

What are the steps I would take to find the closed form expression for the following recurrence relation?

Answer 1

What you are being asked for is an equation that has $x_n$ on the left side and a formula in $n$ on the right side containing just familiar functions like polynomials and exponentials and only finitely many of them.

First, write it like this for simplicity: $S_0=0$, $S_1=3$, $S_n=S_{n-1}+6S_{n-2}$.

Now, let's suppose there is a solution of the form $S_n=x^n$ for some $x$.

Then the equation says $x^n=x^{n-1}+6x^{n-2}$, simplifies to $x^2-x-6=0$,

which undoubtedly you would be able to solve.

You'll get two values of $x$ that work, let's call them $x_1$ and $x_2$, and then anything of the form $$\alpha x_1^n+\beta x_2^n$$ will work also, for any numbers $\alpha$ and $\beta$.