2
$\begingroup$

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.

  • 0
    You might have a look at some similar posts, like http://math.stackexchange.com/questions/906584/the-number-3-sqrt5n3-sqrt5n-is-an-integer2015-11-05

2 Answers 2

4

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

  • 0
    It took me awhile to figure out what you wanted me to do, but I think I got it now. Thanks so much!2012-07-24
3

Hint $\rm\quad \phi^{\:n+1}\!-\:\bar\phi^{\:n+1} =\ (\phi+\bar\phi)\ (\phi^n-\:\bar\phi^n)\ -\ \phi\:\bar\phi\,\ (\phi^{\:n-1}\!-\:\bar\phi^{\:n-1})$

Therefore, upon substituting $\rm\ \phi+\bar\phi\ =\ 1\ =\, -\phi\bar\phi\ $ and dividing by $\:\phi-\bar\phi = \sqrt 5\:$ we deduce that $\rm\:f_{n+1} = f_n + f_{n-1}.\:$ Since $\rm\:f_0,f_1\:$ are integers, all $\rm\,f_n\:$ are integers by induction, using the recurrence.