Question

Prove that the \(n^{th}\) term of the Fibonacci sequence \(a_n\) is the closest integer to \(\phi^n/\sqrt5\) where\[\phi=\frac{1+\sqrt5}2\]is the golden ratio.
Hint: Let \[\psi=\frac{1-\sqrt5}2\]and use mathematical induction and the definition of the Fibonacci sequence to show that \[a_n=\frac{\phi^n-\psi^n}{\sqrt5}\]

Answer 1

So I showed it true for n=1, then assumed it true for some k, then started with\[\frac{\phi^k-\psi^k}{\sqrt5}+\frac{\phi^{k-1}-\psi^{k-1}}{\sqrt5}\]trying to show that this equals\[\frac{\phi^{k+1}-\psi^{k+1}}{\sqrt5}=a_{k+1}\]but I am having little luck. Ideas?

Answer 2

Have you brought in the definition of the fibonacci sequence in to the proof yet?

Answer 3

yeah, that's why I have the first line there above

Answer 4

\[a_{k}+a_{k-1}=\frac{\phi^k-\psi^k}{\sqrt5}+\frac{\phi^{k-1}-\psi^{k-1}}{\sqrt5}\]which I am trying to show equals \(a_{k+1}\), which is the definition of the Fibonacci sequence.

Answer 5

From where you left off with the "k + 1", I bring in the definition of the fibonacci number:\[\bf a_n=\frac{ \phi^n - (1-\phi)^n }{ \sqrt{5} }\]Where \(\bf \phi=\frac{1+\sqrt{5}}{2}\). If we let n = t = k + 1, where n, t, k are all integers, we can re-write the definition as:\[\bf a_{k+1}=\frac{ \phi^{k+1} - (1-\phi)^{k+1} }{ \sqrt{5} }=\bf a_t=\frac{ \phi^t - (1-\phi)^t }{ \sqrt{5} }\]Now note the following:\[\bf (1-\phi)^t=(\psi)^t \implies \left( 1-\frac{1+\sqrt{5}}{2} \right)^t=\left( \frac{1-\sqrt{5}}{2} \right)^t\]Re-arranging the the left-hand-side we obtain that:\[\bf \left( \frac{1-\sqrt{5}}{2} \right)^t=\left( \frac{1-\sqrt{5}}{2} \right)^t \implies L.H.S=R.H.S\]Now that we have validated this, it is clear to see that:\[\bf a_{k+1}=\frac{ \phi^{k+1} - (1-\phi)^{k+1} }{ \sqrt{5} }=\frac{ \phi^{t} - (1-\phi)^{t} }{ \sqrt{5} }=\frac{ \phi^{k+1} - \psi^{k+1} }{ \sqrt{5} }\]@TuringTest

Answer 6

@TuringTest

Answer 7

Wow, sorry, my connection went out for a while. Very nice solution @genius12 , thanks!

Answer 8

No problem.