Why is $\frac{1}{\sqrt 5}\left[\left(\frac{1+\sqrt 5}{2}\right)^n-\left(\frac{1-\sqrt 5}{2}\right)^n\right]$ an integer? 
I am looking for a proof on why 
  $$\frac{1}{\sqrt 5}\left[\left(\frac{1+\sqrt 5}{2}\right)^n-\left(\frac{1-\sqrt 5}{2}\right)^n\right]$$
  an integer.

I have seen many proofs on this, but they all refer to a properties of Fibonacci numbers, which shouldn't be necessary.
I am trying to see why it is true using purely elementary results such as the binomial formula. Clearly this reduces to 
$$\frac{1}{2^n\sqrt 5}\sum_{k=0}^n {n\choose k }\left(1-(-1)^k\right) 5^{k/2}$$ 
I am looking for a "divisibility" argument to see why this is an integer. 
 A: One of the easiest proofs goes by induction.


*

*Set $a= \frac{1+\sqrt{5}}{2}$ and $b= \frac{1-\sqrt{5}}{2}$
Then you have
$$ab = -1 \mbox{ and } a+b = 1$$
Induction start $n= 1$: $\frac{1}{\sqrt 5}\left(a-b\right) = 1$ (Note, that for $n=0$ it is trivially true.)
Induction hypothesis: $\frac{1}{\sqrt 5}\left(a^k-b^k\right)$ is integer for $0\leq k \leq n$.
Induction step $n\to n+1$ ($n \geq 1$):
\begin{eqnarray} \frac{1}{\sqrt 5}\left(a^{n+1}-b^{n+1}\right)
& = & \frac{1}{\sqrt 5}\left((a+b-b)a^{n}-(b+a-a)b^{n}\right) \\
& = & \frac{1}{\sqrt 5}\left((a+b)(a^{n}-b^{n})-ba^n + ab^n \right) \\
& = & \underbrace{\frac{1}{\sqrt 5}\left((a+b)(a^{n}-b^{n})\right)}_{integer} + \frac{1}{\sqrt 5}\left(-\underbrace{ba}_{=-1}a^{n-1} + \underbrace{ab}_{=-1}b^{n-1} \right) \\
& = & \underbrace{\frac{1}{\sqrt 5}\left((a+b)(a^{n}-b^{n})\right)}_{integer} + \underbrace{\frac{1}{\sqrt 5}\left(a^{n-1} - b^{n-1} \right)}_{integer} \\
\end{eqnarray}
A: Since $(1\pm\sqrt5)/2$ are both algebraic integers, so is $$\alpha=\left({1+\sqrt5\over2}\right)^n-\left({1-\sqrt5\over2}\right)^n$$ and since $\alpha$ is of the form $c\sqrt5$ with $c$ rational, $c$ must be an integer. 
We use here this well-known fact: the algebraic integers of the form $(a+b\sqrt5)/2$ are precisely those where $a$ and $b$ are integers of the same parity. 
If you insist on purely elementary methods, you can prove it for $n=0$ and $n=1$, and then use induction, after showing that the numbers for $n=k$ and for $n=k+1$ add up to the number for $n=k+2$. 
