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.

$\endgroup$
  • $\begingroup$ What you need for the induction is $F_n = F_{n-1}+F_{n-2}$. So once you know $F_0$ and $F_1$ are integers, you can use induction to get all $F_n$ are integers. $\endgroup$ – GEdgar Nov 5 '15 at 20:42
  • $\begingroup$ You might have a look at some similar posts, like math.stackexchange.com/questions/906584/… $\endgroup$ – Martin Sleziak Nov 5 '15 at 20:55
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It took me awhile to figure out what you wanted me to do, but I think I got it now. Thanks so much! $\endgroup$ – laser295 Jul 24 '12 at 0:04
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.