Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

You aren't, that was the point. The calculation is purely algebraic. Fib(n) = (φ^n + (1-φ)^n) / √5, so since √5 = -1 + 2φ, we can multiply by this in the numerator and denominator to get (φ^n + (1-φ)^n) (-1+2φ) / 5.

Now expand this as a polynomial and use the identity φ^2 = φ+1 to rewrite all the terms of degree > 1 and we have an expression A+Bφ, and since the Fibonacci numbers are integers, B will be zero, so the answer is A.



Ah sorry my question was rhetorical and I didn't expect an answer. I was just highlighting the fact that this simple looking formula is not a good way to calculate the Fibonacci numbers in practice because you are pushing the complexity of the calculations into highly precise golden ratio.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: