Proof of sequence formula I need help solving the following exercise:

The sequence $(a_n)_{n\in \mathbb N}$ is given by 
  $$a_0 = a_1 = 1 \quad \text{and} \quad a_n=2a_{n-1}+4a_{n-2} \quad \forall n \geq 2$$
  Proof the explicit formula
  $$a_n = \frac{1}{2}((1+\sqrt{5})^n + (1-\sqrt{5})^n) \quad \forall n\in \mathbb N$$

I think the way to go is by induction over n, however I didn't really know what do to after I plugged in everything. I couldn't get $n+1$ into the exponent. Can you guys give me a hint?
 A: Use an ansatz of the type $a_n=A^n$ and plug this into the equation to get $A^n=2A^{n-1}+4A^{n-2}$ or $A^2=2A+4$. Now, solve for $A$ by solving the quadratic equation to get the two soltions $A_{1,2}$. The general solution is given by $a_n=\alpha A_1^n+\beta A_2^n$. Determine $\alpha$ and $\beta$ by using $a_0=a_1=1$.
A: Hint:
Note that $\phi = \frac{1+\sqrt{5}}{2}$ satisfies $\phi^2 = \phi + 1$, and so by multiplying both sides by $\phi^{n-1}$ you have the relation $$\phi^{n+1} = \phi^{n} + \phi^{n-1}$$
Now find a similar expression for $1 - \phi = -\frac{1}{\phi}$ and use
\begin{align*}
a_{n+1} &= 2a_{n} + 4a_{n-1} \\
&= (1+\sqrt{5})^n + (1-\sqrt{5})^n + 2(1+\sqrt{5})^{n-1} + 2(1-\sqrt{5})^{n-1} \\
&= 2^n \left[ \phi^{n} + \phi^{n-1} + (1-\phi)^{n} + (1-\phi)^{n-1} \right]
\end{align*}
A: The method presented by MrYouMath is called characteristic polynomial. 
Another method is by using generating functions. E.g. $$f(x)=\sum_{n=0}^{\infty } a_nx^n=a_0+a_1x+\sum_{n=2}^{\infty } (2a_{n-1}+4a_{n-2})x^n=$$
$$a_0+a_1x+\sum_{n=2}^{\infty } 2a_{n-1}x^n + \sum_{n=2}^{\infty } 4a_{n-2}x^n=$$
$$a_0+a_1x+2x\sum_{n=1}^{\infty } a_{n}x^{n}+4x^2\sum_{n=0}^{\infty }a_{n}x^{n}=$$
$$a_0+a_1x-2xa_0+2xf(x)+4x^2f(x)=1-x+2xf(x)+4x^2f(x)$$
or $$f(x)=\frac{x-1}{4x^2+2x-1}=\frac{x-1}{4\left(x+\frac{1+\sqrt{5}}{4}\right)\left(x+\frac{1-\sqrt{5}}{4}\right)}=$$
$$\frac{1}{4(a-b)}\left( \frac{1-4b}{1-4xb} - \frac{1-4a}{1-4xa} \right)=\frac{1}{4(a-b)}\left( (1-4b)\sum_{n=0}^{\infty }4^nb^nx^n - (1-4a)\sum_{n=0}^{\infty }4^na^nx^n\right)$$
where $a=\frac{1+\sqrt{5}}{4}$ and $b=\frac{1-\sqrt{5}}{4}$. Then
$$a_n=\frac{1}{4(a-b)}\left((1-4b)4^nb^n -(1-4a)4^na^n \right)=$$
$$\frac{1}{2\sqrt{5}}\left( (1-1+\sqrt{5})(1-\sqrt{5})^n -(1 -1 -\sqrt{5})(1+\sqrt{5})^n \right)=\frac{1}{2}\left( (1+\sqrt{5})^n + (1-\sqrt{5})^n \right)$$
Here is another example for Fibonacci sequence.
