<s>[INST] 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?
 [/INST] 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.
</s>