# Why does this test for Fibonacci work?

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?

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.