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

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

-
As presently written, this is not a recursion. – Ron Gordon Jan 23 '13 at 19:46
Yes I did, sorry I'll fix it. – Unknown Jan 23 '13 at 19:48
– Mhenni Benghorbal Jan 23 '13 at 19:53

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.

-

As pointed out by pre-kidney, the characteristic polynomial associated with the given recurrence is $\displaystyle x^3-3x^2-6x+8\color{grey}{=(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 $\left\{\left((-2)^n\right)_{n\in \mathbb{N_0}},\left(1^n\right)_{n\in \mathbb{N_0}},\left(4^n\right)_{n\in \mathbb{N_0}}\right\}$, which means your recurrence 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 $$(\forall n\in \Bbb N_0)\left(t_n=2(-2)^n+2\cdot1^n-4^n=(-1)^n2^{n+1}-4^n+2\right).$$

-