It's the tip of the iceberg though - generatingfunctionology is worth inspecting thoroughly.
(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.
In either case, if you enjoyed this post add one to the "I-should-read-TAOCP" (or "I-should-continue-reading-TAOCP") tally. I did...