Find the solution of the recurrence relation $a_{n}=a_{n - 1} +2a_{n-2}$, $n > 2$ with $a_0 = 0$, $a_1 = 1$.

Question

I am unable to figure this one out, it seems $3^{n-1}$ should be the solution but it does not work for $a_{0}$

Answer 1

This is the well-known Jacobsthal sequence with the solution

$$ a_n=\frac{2^n-(-1)^n}{3} $$

In terms of getting that result for yourself, see the method that I have previously described here. This method is valid for any sequence of the form

$$ f_n=af_{n-1}+bf_{n-2}. $$

Answer 2

$a_{n}=a_{n - 1} +2a_{n-2}$, $n > 2$ with $a_0 = 0$, $a_1 = 1$.

Writing its characteristic equation;

$$x^2-x-2=0$$

Writing its characteristic roots;

$$x_1=2,x_2=-1$$

Writing its general solution;

$$a_n=c_1x_1^n+c_2x_2^n$$

$$a_n=2^nc_1+c_2(-1)^n$$

Using the initial conditions to get the solution;

$$c_1=\frac{1}{3},c_2=\frac{-1}{3}$$

$$a_n=2^n\frac{1}{3}+\frac{-1}{3}(-1)^n$$

$$a_n=\frac{1}{3}\left[2^n-(-1)^n\right]$$