Proof that $\frac{(1+\sqrt 5)^n+(1-\sqrt 5)^n}{2^n}$ is an integer

Question

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.

Answer 1

Hint: $$\alpha^{n+1} + \beta^{n+1} = (\alpha^n + \beta^n)(\alpha + \beta) - \alpha\beta(\alpha^{n-1}+\beta^{n-1}).$$

In your case, $\alpha + \beta$ and $\alpha\beta$ happen to be integers.

Answer 2

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.