<s>[INST] The number $\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$ is always an integer For each $n$ consider the expression $$\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$
I am trying to prove by induction that this is an integer for all $n$.
In the base case $n=1$, it ends up being $1$. 
I am trying to prove the induction step:


*

*if $\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$ is an integer, then so is
$\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right]$.


I have tried expanding it, but didn't get anywhere.
 [/INST] Try writing
$$
\left(\frac{1+\sqrt{5}}{2}\right)^n = \frac{a_n+b_n\sqrt{5}}{2}
$$
with $a_1=b_1=1$ and
$$
\frac{a_{n+1}+b_{n+1}\sqrt{5}}{2} = \left(\frac{1+\sqrt{5}}{2}\right)\left(\frac{a_n+b_n\sqrt{5}}{2}\right)
$$
see what you get, then repeat as much as you need to with $\left(\frac{1-\sqrt{5}}{2}\right)^n$.
</s>