Hacker News new | past | comments | ask | show | jobs | submit login

I've always preferred to write Binet's formula like this:

(phi^n - psi^n)/(phi - psi)

The only difference is writing the sqrt(5) denominator as phi-psi. The reason being, this exhibits that the Fibonacci numbers are a symmetric function of the roots of a polynomial. Thus, even though phi and psi involve irrational numbers, this symmetric function of them must be in the base rational field, and since the polynomial x^2 - x - 1 is monic, then these are plain integers.

This way it looks less surprising that a formula involving irrationals is always rational.

To show that the rational is actually an integer, you have to actually perform the division to get

phi^n + phi^(n-1) psi + phi^(n-2) psi^2 + ... + psi^n

and use the fact that algebraic integers form a ring and the only rational algebraic integers are plain integers.

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