Recursive sequence is sequence of integers

Define the following recursive sequence:

$$\begin{cases} a_1&=&1 \\ a_{n+1}&=&\displaystyle \frac{a_n+\sqrt{5a_n^2+4(-1)^n}}2\ \left(n\in\mathbb Z^+\right)\end{cases}$$

Prove that $a_n$ is an integer for all $n\in\mathbb Z^+$.

In fact it turns out that $\left(a_n\right)_{n=1}^\infty$ is the Fibonacci sequence 1, 1, 2, 3, 5, 8, .... I have actually solved this problem before but now I just can't recall what the solution is! It seems odd asking a question I've already solved, but the fact that I can't remember how I did it is bugging me. Please help me.

Notice that $a_{n+1}$ is a root of the quadratic equation $x^2-a_nx-[a_n^2+(-1)^n]$, i.e. $$a_{n+1}^2-a_na_{n+1}-[a_n^2+(-1)^n]\ =\ 0$$ Treating the above as a quadratic in $a_n$ instead (and noting that $a_n>0$) gives $$\begin{array}{rcl}a_n& =& \dfrac{-a_{n+1}+\sqrt{5a_{n+1}^2-4(-1)^n}}2 \\ &=& -a_{n+1}+\dfrac{a_{n+1}+\sqrt{5a_{n+1}^2+4(-1)^{n+1}}}2 \\ &=& -a_{n+1}+a_{n+2}\end{array}$$ Hence the $a_n$ are Fibonacci numbers and therefore all integers.