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

@Manu Sm I have edited your question. I assumed that the last index in your recurrence relation needs to $n-2$ instead of $n-1$, otherwise the question has no solutions... Can you verify that this edit is correct? — Ernie060, Oct 22 '23 at 08:53
If the hypothesis is $a_{n}=a_{n - 1} +2a_{n-2}$, then from this we infer $a_n-2a_{n-1}=-(a_{n-1}-2a_{n-1})$, which implies $b_n={a_n-a_{n-1}}$ is an geometric sequence with $b_1=a_1-a_0=1$ $\implies$ $a_n-2a_{n-1}=(-1)^{n-1}=-(-1)^n$ $\implies$ $a_n+\frac{1}{3}(-1)^n=2a_{n-1}-\frac{2}{3}(-1)^n=2(a_{n-1}+\frac{1}{3}(-1)^{n-1})$ $\implies$ $c_n=a_n+\frac{1}{3}(-1)^n$ is a geometric sequence with $q=2$, $c_0=\cdots$ — Asigan, Oct 22 '23 at 09:09
Are you familiar with the recurrence relations with constant coefficients method ? First you look for solutions of the form $x^n$ and then you combine them to satisfy the initial conditions. — Ryszard Szwarc, Oct 22 '23 at 09:26
@Ernie060 I guess, looking from other comments , there is some mistake in my assignment in that case, the question most probably was erroneous and your edit might be the right correction. — Manu Sm, Oct 23 '23 at 09:14

score 1 · Answer 1 · answered Oct 23 '23 at 04:14

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

score 0 · Answer 2 · answered Oct 22 '23 at 23:33

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

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

2 Answers2