nth element of recurrence relation

Question

I need to find explicit equation, that will give me n-th element of this recurrence: $$ a_0=0\\ a_1=3\\ a_{n+2}=a_{n+1} + 2a_{n} $$ I know, that I can use generating functions and difference equations, but I don't really know how to approach this problem.

Answer 1

If you are familiar with homogenic recursions:

You can write the characteristic equation: $x^{n+2} = x^{n+1}+2x^n \rightarrow x^2=x+2 \rightarrow x^2-x-2=0$. Your solutions are: $x_1=2, x_2=-1$. Therefore, your recursion have the followning form. $x_n = \alpha * 2^n + \beta *(-1)^n$

Now, to make it correct, we need to get $\alpha$ and $\beta$ with your starting elements:

$x_0 = 0 \rightarrow \alpha + \beta= 0, x_1=3 \rightarrow 2\alpha-\beta= 3$. Solutions: $\alpha = 1, \beta = -1$

Therefore, your recurrence will look like: $x_n = 1*2^n + (-1)*(-1)^n \rightarrow 2^n + (-1)^{n+1}$

Answer 2

First Step

Write the equation in standard form.

$$a_{n+2} - a_{n+1} -2a_n = 0$$

Now write the characteristic equation.

$$r^2 - r - 2 = 0$$ $\iff r_1 = 2 $ & $r_2 = -1$

Thus we know the general form of the homogeneous equation is:

$$a_n = c_1{2}^n + c_2({-1})^n$$

Second Step

Use the initial conditions.

$$a_0 = 0$$ $$a_1 = 3$$

We get:

\begin{cases} c_1 + c_2 = 0 \\ 2c_1 -c_2 = 3 \end{cases}

Solving the system gives:

$c_1 = 1$ $c_2 = -1$

Thus

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

Answer 3

Define $A(x)=\sum_{n\ge 0} a_n x^n$ as the generating function for $(a_n)$. Then, the given recurrence gives you, $$A(x)-(a_1x+a_0)=x(A(x)-a_0)+2x^2A(x)\\\implies A(x)=\frac{-3x}{2x^2+x-1}=-\frac{3x}{(2x-1)(x+1)}=\left(\sum_{n\ge 0}(2x)^n-(-1)^nx^n\right)\\\implies a_n=(2^{n}+(-1)^{n+1}),\ n\ge 1$$