Finding a sequence satisfying this recurrence relation?

Question

I just don't even know where to start with this,

Find a sequence $(x_n)$ satisfying the recurrence relation:

$2x_n$$_+$$_2$ = $3x_n$$_+$$_1$ + $8x_n$ + $3x_n$$_-$$_1$ Where n is a natural number and

$x_0$ = -1, $x_1$ = 3 and $x_2$ = 3

Thanks in advance!

Answer 1

Hint: Look for solutions of the form $\lambda^n$. Note also that linear combinations of solutions are also solutions.

Answer 2

Let $2x_{n+2} = 3 \, x_{n+1} + 8 \, x_{n} + 3 \, x_{n-1}$, with $x_{0} = -1, x_{1} = 3$ and $x_{2} = 3$ for which letting $x_{n} = p^{n}$ the equation $$2 \, p^{3} - 3 \, p^{2} - 8 \, p - 3 = 0$$ is obtained. This equation can be factored to $(p-3)(p+1)(2p+1) = 0$ and leads to the roots $p \in \{ 3, -1, -1/2 \}$. From this the general form of $x_{n}$ is $$x_{n} = a_{0} \, 3^{n} + a_{1} \, (-1)^{n} + a_{2} \, \left( - \frac{1}{2} \right)^{n}.$$ Applying the initial conditions yields: \begin{align} -1 &= a_{0} + a_{1} + a_{2} \\ 3 &= 3 \, a_{0} - a_{1} - \frac{a_{2}}{2} \\ 3 &= 9 \, a_{0} + a_{1} + \frac{a_{2}}{4} \end{align} which leads to $a_{0} = \frac{1}{2}$, $a_{1} = - \frac{3}{2}$, $a_{2} = 0$. The resulting sequence is generated by \begin{align} x_{n} = \frac{3}{2} \, \left( 3^{n-1} + (-1)^{n-1} \right) \end{align}

Answer 3

A general way to solve such is using generating functions. Define:

$\begin{align*} g(z) &= \sum_{n \ge 0} x_n z^n \end{align*}$

Write your recurrence shifted (subtraction in indices gets messy), multiply by $z^n$, sum over $n \ge 0$ and recognize resulting sums:

$\begin{align*} 2 x_{n + 3} &= 3 x_{n + 2} + 8 x_{n + 1} + 3 x_n \\ 2 \sum_{n \ge 0} x_{n + 3} z^n &= 3 \sum_{n \ge 0} x_{n + 2} z^n + 8 \sum_{n \ge 0} x_{n + 1} z^n + 3 \sum_{n \ge 0} x_n z^n \\ 2 \frac{g(z) - x_0 - x_1 z - x_2 z^2}{z^3} &= 3 \frac{g(z) - x_0 - x_1 z}{z^2} + 8 \frac{g(z) - x_0}{z} + 3 g(z) \end{align*}$

Solve this for $g(z)$ (substitute the initial values), express as partial fractions:

$\begin{align*} g(z) &= \frac{1 - 5 z}{1 - 2 z - 3 z^2} \\ &= \frac{1 - 5 z}{(1 + z) (1 - 3 z)} \\ &= - \frac{3}{2 (1 + z)} + \frac{1}{2 (1 - 3 z)} \end{align*}$

We want the coefficient of $z^n$ of this. But this is just two geometric series:

$\begin{align*} [z^n] g(z) &= - \frac{3}{2} (-1)^n + \frac{1}{2} \cdot 3^n \\ &= \frac{3^n - (-1)^n}{2} \end{align*}$