Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 7 down vote accepted

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.

share|cite|improve this answer
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.