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?

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}

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$.