# Thread: Solving this recurrence relation

1. ## Solving this recurrence relation

Solve the recurrence relation an = an-1 + 2an-2 with initial conditions a0 = a1 = 1 by making the substitution bn = an.

I made the substitution from the beginning. Never seen an example like this. My working...

bn = 1bn-1 + 2bn-2

Characteristic equation form: x2 = ax + b implies x2 = 1x + 2

x2 -x -2 = 0

(x - 2)(x + 1) = 0

x = 2, -1.

General solution is bn = A(2)n + B(-1)n

When n = 0; b0 = a0 = 1 = 1.

1 = A(2)0 + B(-1)0
1 = A(1) + B

When n = 1; b1 = a1= 1 = 1.

1 = A(2)1 + B(-1)1
1 = 2A - B

Solving simultaneous equations...

A = 2 / 3.

B = 1 / 3.

Solution is (2/3)2n + (1/3)(-1)n.

Method is correct?

2. ## Re: Solving this recurrence relation

Method looks fine to me, barring a final answer for $\displaystyle a_n$.

3. ## Re: Solving this recurrence relation

Let's check:

$\sqrt{\dfrac{2}{3}2^n+\dfrac{1}{3}(-1)^n} = \sqrt{\dfrac{2}{3}2^{n-1}+\dfrac{1}{3}(-1)^{n-1}}+2\sqrt{\dfrac{2}{3}2^{n-2}+\dfrac{1}{3}(-1)^{n-2}}$?

Try with $n=2$:

$\sqrt{3} = \sqrt{1}+2\sqrt{1}$ is false.

Instead, you need to use the fact that $b_n = \sqrt{a_n}$ implies

$a_n = b_n^2 = \left(\dfrac{2}{3}2^n+\dfrac{1}{3}(-1)^n\right)^2 = \dfrac{4}{9}4^n+\dfrac{4}{9}(-2)^n+\dfrac{1}{9}$

Now, we test:
$a_0 = \dfrac{4}{9}+\dfrac{4}{9}+\dfrac{1}{9} = 1$ check
$a_1 = \dfrac{16}{9}-\dfrac{8}{9}+\dfrac{1}{9} = 1$ check
$\sqrt{a_n} = \sqrt{a_{n-1}}+2\sqrt{a_{n-2}}$ satisfied by construction. Check.

Yup, that's the solution.

4. ## Re: Solving this recurrence relation

Right, if I squared my solution; it would've been fine for an​.