Prove Fib(n) is closest integer to golden ratio

141 Views Asked by At

Does anyone know why it's suggested this proof use $\psi = (1 - \sqrt 5)/2$? I'm a bit lost here. Guidance appreciated.

PROOF Link

Start of Proof

1

There are 1 best solutions below

1
On

Is it clear for you why $Fib(n)=(\phi^n-\psi^n)/\sqrt{5}$? If not, try here:

https://en.wikipedia.org/wiki/Constant-recursive_sequence#Fibonacci_sequence

When that's done, you should apply Tanner's hint to see that: $$\mid\psi\mid<1 \implies \mid Fib(n)-\phi^n/\sqrt{5}\mid=\mid\psi\mid^n/\sqrt{5} < 1, $$