8
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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 :-) $\endgroup$ – Jyrki Lahtonen Feb 11 '14 at 11:46
  • 5
    $\begingroup$ 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. $\endgroup$ – Daniel Fischer Feb 11 '14 at 11:51
  • 1
    $\begingroup$ @DanielFischer: That should be an answer! $\endgroup$ – m0nhawk Feb 11 '14 at 11:51
  • 1
    $\begingroup$ How do you proved that $F_n$ is rational? Binomial theorem? $\endgroup$ – Martín-Blas Pérez Pinilla Feb 11 '14 at 11:53
  • 3
    $\begingroup$ @Martín-BlasPérezPinilla That, or shorter, it is conjugation-invariant. $\endgroup$ – Daniel Fischer Feb 11 '14 at 11:55
12
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.