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

Question

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.

Answer 1

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

Answer 2

Hint $\rm\ \ \ \phi^{\:n+1}\!-\:\bar\phi^{\:n+1} =\ (\color{#0a0}{\phi+\bar\phi})\ (\phi^n-\:\bar\phi^n)\ \color{#c00}{-\ \phi\:\bar\phi}\,\ (\phi^{\:n-1}\!-\:\bar\phi^{\:n-1})\ $ by here.

Substituting $\rm\ \color{#0a0}{\phi+\bar\phi}\, =\ 1\, =\, \color{#c00}{-\phi\bar\phi}\ $ then dividing by $\:\phi-\bar\phi = \sqrt 5\:$ the above becomes $\rm\:f_{n+1} = f_n + f_{n-1}\,$ so $\rm\,f_0,\:\!f_1\in\Bbb Z\,\Rightarrow\, $ all $\rm\,f_n\in\Bbb Z\,$ by induction, using the recurrence.