# Solving recurrence relation: What am I missing in my working?

Apologies for the uninformative title, this is a relatively specific question so it was hard to title.

I'm solving the following recurrence relation:

$a_{n} + a_{n-1} - 6a_{n-2} = 0$
With initial conditions $a_{0} = 3$ and $a_{1} = 1$

And I have it mostly figured out except for the very last part.

My working:

We have characteristic equation $s^2 + s - 6 = 0$ This factorises to $(s+3)(s-2)$
Hence we have roots $s=-3$ and $s=2$

and hence the solution has the form $a_{n} = -x3^n + y2^n$

We sub in the initial conditions:

$a_{0} = x + y = 3$
$a_{1} = -3x+2y = 1$

And solving this system we have solutions:
$x = 1$ and $y = 2$

Hence subbing this back to what we work out to be the general form of the solution:

$a_{n} = (-1)3^n + (2)2^n$
$a_{n} = (-3)^n + (4)^n$ Correct?

But it is incorrect, the correct solution is:

$a_{n} = (-3)^n + 2^{n+1}$

I don't understand where the $2^{n+1}$ came from. What am I missing here?

-

You can't multiply expressions with exponents like that. $2\times (2^n)$ is equal to $2^{n+1}$, not $$4^n=\underbrace{4\times\cdots\times 4}_{n\text{ times}}=\underbrace{(2\times 2)\times\cdots\times (2\times 2)}_{n\text{ times}}=\underbrace{2\times\cdots\times 2}_{2n\text{ times}}=2^{2n}.$$

Also, the general solution is $$a_n=x(-3)^n+y2^n,$$ which is not the same as $-x3^n+y2^n$, which is what you wrote in the question. It so happens that since $x$ is 1, this discrepancy did not cause a problem, but you should be aware of the issue in general.

-
It was supposed to be $1 \times (-3)^n$ in the first place, not $(-1) \times 3^n$. (Ah, you edited. My point still applies to the original post though.) – anon Jun 19 '11 at 5:56
oh god, yes, of course it's not $4^n$. Completely forgotten about index laws. thanks – Arvin Jun 19 '11 at 6:00
@Arvin: No problem. Also, I edited again, since there was still an issue with the 3 part I wanted to mention. – Zev Chonoles Jun 19 '11 at 6:03
The discrepancy was just pure carelessness on my part (yet another one) Thanks for pointing it out, I'll watch out for them from now on :) – Arvin Jun 19 '11 at 6:05

$(2)2^n$ is equal to $2^{n+1}$, not to $4^n$.

-