Find a formula for the nth term of the sequence defined by the third-order recursion:

Question

$t_{n+2} = 3t_{n+1} + 6t_n – 8t_{n–1}$

with initial values $t_0 = 3, t_1 = t_2 = –6$

You don't have to give me the answer, please just try and point me in the right direction.

Answer 1

The general approach is to start with the characteristic polynomial associated with your recurrence $$x^3-3x^2-6x+8$$ Now, find its roots. Then, the solution can be written as a sum of geometric series expressions, with common factors given by the roots you obtained.

See here: http://mathcircle.berkeley.edu/BMC3/Bjorn1/node4.html for instance.

Answer 2

As pointed out by pre-kidney, the characteristic polynomial associated with the given recurrence is $\displaystyle x^3-3x^2-6x+8=(x-(-2))(x-1)(x-4)$.

Since the roots of the characteristic polynomial are all simple and real, a basis of solutions to the recurrence is $\{((-2)^n)_{n\in \mathbb{N_0}},(1^n)_{n\in \mathbb{N_0}},(4^n)_{n\in \mathbb{N_0}}\}$, which means your recurrence $t_n$ is such that, for all $n\in \mathbb{N_0}$,

$$t_n=\alpha (-2)^n+\beta \cdot1^n+\gamma 4^n$$

for some $\alpha ,\beta ,\gamma$ yet to be determined. To find them use the initial conditions. You'll get the linear system:

\begin{cases} t_0=3=\alpha +\beta +\gamma \\ t_1=-6=-2\alpha+\beta + 4\gamma \\ t_2=-6=4\alpha + \beta + 16\gamma \end{cases}

And the only solution will be $\alpha =2, \beta =2, \gamma =-1$, therefore $$t_n=2(-2)^n+2\cdot1^n-4^n=(-1)^n2^{n+1}-4^n+2$$