<s>[INST] Proof that $\frac{(1+\sqrt 5)^n+(1-\sqrt 5)^n}{2^n}$ is an integer I want to prove, by induction, that
$$\frac{(1+\sqrt 5)^n+(1-\sqrt 5)^n}{2^n}\quad\text{is an integer}.$$
Instinctively, this sort of thing looks like the solution of a second order recurrence relation (like the explicit formula for the Fibonacci sequence), but I want to prove it directly, without invoking that I know that.
But induction doesn't seem to be working, since
\begin{gather*}
    \frac{(1+\sqrt 5)^n+(1-\sqrt 5)^n}{2^n}\\[8pt] = \frac 12\bigg(\frac{(1+\sqrt 5)^{n-1}+(1-\sqrt 5)^{n-1}}{2^{n-1}} + \frac{\sqrt 5}2\cdot \frac{(1+\sqrt 5)^{n-2}-(1-\sqrt 5)^{n-2}}{2^{n-2}} + \frac q2\cdot\frac{(1+\sqrt 5)^{n-2}+(1-\sqrt 5)^{n-2}}{2^{n-2}}\bigg),
\end{gather*}
so I can deal with the first and last terms using the induction hypothesis, but not the middle one.
I suppose I can "strengthen" the induction hypothesis by proving simultaneously that
$$\text{Both}\quad\frac{(1+\sqrt 5)^n+(1-\sqrt 5)^n}{2^n}\quad\text{and}\quad \sqrt 5\frac{(1+\sqrt 5)^n-(1-\sqrt 5)^n}{2^n}\quad \text{are integers},$$
but again it feels like a direct approach should be possible.
 [/INST] You have\begin{multline}\frac{\left(1+\sqrt5\right)^{n+1}+\left(1-\sqrt5\right)^{n+1}}{2^{n+1}}-\frac{\left(1+\sqrt5\right)^n+\left(1-\sqrt5\right)^n}{2^n}=\\=\frac{\left(-1+\sqrt5\right)\left(1+\sqrt5\right)^n+\left(-1-\sqrt5\right)\left(1-\sqrt5\right)^n}{2^{n+1}}=\\=\frac{\left(1+\sqrt5\right)^{n-1}+\left(1-\sqrt5\right)^{n-1}}{2^{n-1}},\end{multline}since $\left(-1+\sqrt5\right)\left(1+\sqrt5\right)=\left(-1-\sqrt5\right)\left(1-\sqrt5\right)=4=2^2$. Therefore, if$$a_n=\frac{\left(1+\sqrt5\right)^n+\left(1-\sqrt5\right)^n}{2^n},$$you have $a_{n+1}=a_n+a_{n-1}$. So, since $a_0=2$ and $a_1=1$, each $a_n$ is a non-negative integer.
</s>