# Prove my induction (Golden Ratio)

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

-
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

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