1.2.2. Tree Recursion
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.