Solução: Vamos provar por indução que Fib(n) = (φn-ψn)/√5. Temos Fib(0)= 0 =(φ0-ψ0)/√5, e Fib(1)= 1 = (φ1-ψ1)/√5. Juntas, essas afirmações formam a base da indução. Suponhamos que Fib(n) = (φn-ψn)/√5 e, mais ainda, Fib(n+1) = (φn+1-ψ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) = (φn+1-ψn+1)/√5 + (φn-ψn)/√5
Fib(n+2) = ((φn+1+φn) - (ψn+1+ψn))/√5
Fib(n+2) = (φn(φ+1) - ψn(ψ+1))/√5
Porém, como φ+1=φ² e ψ+1=ψ² (é verdade, faça as contas...), temos:
Fib(n+2) = (φn+2-ψn+2)/√5.
Ou seja, provamos por indução que Fib(n)= (φn-ψn)/√5. Mas não é esse o nosso objetivo. O nosso objetivo é mostrar que Fib(n) é o inteiro mais próximo de φn/√5. Para concluir a prova, basta notar que:
- Fib(n)= φn/√5 - ψn/√5
- |ψn|/√5 < 0.5, para todo n não-negativo.
Nenhum comentário:
Postar um comentário