1.2.2. Tree Recursion
Exercise 1.13

Fibonacci numbers and golden ratio

Prove that Fib(n) is the closest integer to φⁿ/√5, where φ = (1 + √5)/2. Hint: Let ψ = (1 - √5)/2. Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that Fib(n) = (φⁿ - ψⁿ)/√5.

There are no comments yet.

Authentication required

You must log in to post a comment.