# How to prove that Fibonacci number is integer?

How to prove that formula for Fibonacci numbers are always integers, for all $n$:

$$F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}$$ where, $\varphi = \frac{1 + \sqrt{5}}{2}$ and $\psi = \frac{1 - \sqrt{5}}{2}$.

I know how to prove that $F_n$ is rational, but what about integer?

-
Is induction an option? $F_0=0$, $F_1=1$, and $F_{n+2}=F_{n+1}+F_n$ thereafter (prove those by brute forcing). I know, apparently you want to use the theory of algebraic integers :-) –  Jyrki Lahtonen Feb 11 '14 at 11:46
Also, noting that $\sqrt{5} = \varphi - \psi$, you have $$F_n = \frac{\varphi^n - \psi^n}{\varphi - \psi} = \sum_{k=0}^{n-1} \varphi^{n-1-k}\psi^k,$$ so $F_n$ is an algebraic integer. As it's also rational, it must be a rational integer. –  Daniel Fischer Feb 11 '14 at 11:51
@DanielFischer: That should be an answer! –  m0nhawk Feb 11 '14 at 11:51
How do you proved that $F_n$ is rational? Binomial theorem? –  Martín-Blas Pérez Pinilla Feb 11 '14 at 11:53
@Martín-BlasPérezPinilla That, or shorter, it is conjugation-invariant. –  Daniel Fischer Feb 11 '14 at 11:55

Since $\sqrt{5} = \varphi-\psi$, we have
$$F_n = \frac{\varphi^n - \psi^n}{\varphi-\psi} = \sum_{k=0}^{n-1} \varphi^{n-1-k}\psi^k.$$
Since $\varphi$ and $\psi$ are algebraic integers, so is $F_n$. A rational algebraic integer must be a rational integer.