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?
Solution 1:
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.