nth element of recurrence relation 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.
 A: 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$$
A: 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}$$
A: 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}$
