SICP - Exercício 1.13 - Termo geral da sequência de Fibonacci

Prove que Fib(n) é o inteiro mais próximo de φⁿ/√5, onde φ = (1+√5)/2. Dica: defina ψ = (1-√5)/2. Use indução e a definição dos números de Fibonacci para provar que Fib(n) = (φⁿ-ψⁿ)/√5.

Solução: Vamos provar por indução que Fib(n) = (φⁿ-ψⁿ)/√5. Temos Fib(0)= 0 =(φ⁰-ψ⁰)/√5, e Fib(1)= 1 = (φ¹-ψ¹)/√5. Juntas, essas afirmações formam a base da indução. Suponhamos que Fib(n) = (φⁿ-ψⁿ)/√5 e, mais ainda, Fib(n+1) = (φⁿ⁺¹-ψⁿ⁺¹)/√5, para todo n não negativo.

Temos, pela definição dos números de Fibonacci:

Fib(n+2) = Fib(n+1) + Fib(n)
Fib(n+2) = (φⁿ⁺¹-ψⁿ⁺¹)/√5 + (φⁿ-ψⁿ)/√5
Fib(n+2) = ((φⁿ⁺¹+φⁿ) - (ψⁿ⁺¹+ψⁿ))/√5
Fib(n+2) = (φⁿ(φ+1) - ψⁿ(ψ+1))/√5

Porém, como φ+1=φ² e ψ+1=ψ² (é verdade, faça as contas...), temos:
Fib(n+2) = (φⁿ⁺²-ψⁿ⁺²)/√5.

Ou seja, provamos por indução que Fib(n)= (φⁿ-ψⁿ)/√5. Mas não é esse o nosso objetivo. O nosso objetivo é mostrar que Fib(n) é o inteiro mais próximo de φⁿ/√5. Para concluir a prova, basta notar que:

1. Fib(n)= φⁿ/√5 - ψⁿ/√5
2. |ψⁿ|/√5 < 0.5, para todo n não-negativo.