# How to prove that Fibonacci number is integer? [duplicate]

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.