36
$\begingroup$

In order to test if a number $A$ is Fibonacci, all we need to do is compute $5A^2 + 4$ and $5A^2 -4$. If either of them is a perfect square, the number is Fibonacci, otherwise not.

Why does this test work? Is there an easy proof?

$\endgroup$
2
32
$\begingroup$

Suppose $A = F_n$ is a Fibonacci number. Then we can easily prove by induction that $$ 5 F_n^2 - L_n^2 = \begin{cases} 4 \qquad &\mbox{if $n$ is odd}; \\ -4 \qquad &\mbox{if $n$ is even}. \end{cases} $$ Here $L_n$ denotes the Lucas sequence, defined by $L_1=1$, $L_2=3$ and $L_{n+2} = L_{n+1} + L_n$. This means that $5F_n^2 \pm 4$ is a square.

Of course the other direction is the interesting one, that is, if $5A^2 \pm 4$ is a square then $A$ is a Fibonacci number. The equation $5A^2\pm 4 = B^2$ rewrites to $$ \pm 1 = \left( \frac{B+A\sqrt5}{2} \right) \left( \frac{B-A\sqrt{5}}{2} \right) $$ and therefore implies that (noting that $A$ and $B$ have the same parity) $\frac{B+A\sqrt5}{2}$ is a unit in $\mathbb{Z}\left[\frac{1+\sqrt{5}}{2}\right]$. By the Dirichlet unit theorem, the unit group of $\mathbb{Z}\left[\frac{1+\sqrt5}{2}\right]$ is of the form $$ \mathbb{Z}\left[\frac{1+\sqrt5}{2}\right]^\ast = \{\pm 1\} \times \langle \eta \rangle = \{\pm 1\} \times \{\eta^k : k\in \mathbb{Z}\} $$ where $\eta$ is a so-called fundamental unit. We can always assume that $\eta = t + u \frac{1+\sqrt5}{2}$ with $t,u \geq 0$. Since $u=1$ already gives a unit $\frac{1+\sqrt5}{2}$, we then have $\eta = \frac{1+\sqrt5}{2}$. Since $\frac{B+A\sqrt5}{2}$, there exists a positive integer $\ell$ such that $$ \frac{B+A\sqrt5}{2} = \left( \frac{1+\sqrt5}{2} \right)^\ell, $$ or $ 2^{\ell-1}(B+A\sqrt5) = (1+\sqrt5)^\ell. $ By taking conjugates, it follows that $ 2^{\ell-1}(B-A\sqrt5) = (1-\sqrt5)^\ell. $ We now see that $$ A = \frac{2^{\ell-1}(B+A\sqrt5) - 2^{\ell-1}(B-A\sqrt5)}{2^{\ell} \sqrt 5} = \frac{(1+\sqrt5)^\ell - (1-\sqrt5)^\ell}{2^{\ell} \sqrt 5} = \frac{1}{\sqrt{5}}\left( \left( \frac{1+\sqrt5}{2} \right)^\ell - \left( \frac{1-\sqrt5}{2} \right)^\ell\right) = F_\ell $$ where we used the Euler-Binet formula for the last step.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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