Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.


I am trying to prove that this equation expression is still divisible by $\sqrt{5}$ when $n+1$.

I've tried expanding it, but didn't get anywhere after that... Any hints would be appreciated. Thanks.

share|cite|improve this question
What is this supposed to equal? What are you trying to prove? –  Ross Millikan Jul 23 '12 at 23:09
Trying to prove by induction, saying that it would still be divisible by sqrt(5) when n+1 –  laser295 Jul 23 '12 at 23:10
I think the OP's ultimately trying to prove this is equal to the $n^{th}$ Fibonacci number... –  Alex Nelson Jul 23 '12 at 23:11
This is not an equation, it is an expression –  Belgi Jul 23 '12 at 23:22
So you are trying to prove this expression (not equation) is integral (not divisible by $\sqrt 5$, as you have divided by $\sqrt 5$) for all $n$ –  Ross Millikan Jul 23 '12 at 23:25

2 Answers 2

up vote 1 down vote accepted

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

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

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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