Fibonacci sequence $F_n$ is defined recursively in the following way: Let $F_0=0$ and $F_1=1$ we define $F_{i}=F_{i-2}+F_{i-1}$, for any integer $i>2$. Now consider the following numbers: \[ \phi=\frac{1+\sqrt{5}}{2} \quad \mbox{and} \quad \psi=\frac{1-\sqrt{5}}{2} \] This two numbers are strongly related to Fibonacci numbers. The first formula to consider known as ``Binet Formula'': \begin{equation} \tag{1} F_n=\frac{\phi^n-\psi^n}{\phi-\psi} \end{equation}

Consider the sequence
\[ \frac{F_{n+1}}{F_n} \]
What is the limit of this sequence, when $n$ goes to infinity? Does this
sequence converge? Well, it turned out to be that this sequence converges to
the number $\phi$. The number $\phi$, also known as the ''Golden
Ratio'', is a very important number in mathematics appearing everywhere, you can find
it in art, architecture, biology, nature and many many more.

Consider the sum \begin{equation} \sum_{i=0}^n F_i \end{equation} It is easy to see that $\phi-\psi=\sqrt{5}$ and that both $\phi=1-\psi$ and $\psi=1-\phi$. Using these equalities the Binet formula and the formula for geometric series we get \begin{equation} \begin{array}{l} \sum_{i=0}^{n} F_i &= \frac{1}{\sqrt{5}}\sum_{i=0}^n \phi^i-\psi^i \\ &= \frac{1}{\sqrt{5}}\left(\frac{\phi^{n+1}-1}{\phi-1}-\frac{\psi^{n+1}-1}{\psi-1}\right) \\ &= \frac{1}{\sqrt{5}}\left(\frac{(\phi^{n+1}-1)(\psi-1)-(\psi^{n+1}-1)(\phi-1)}{(\phi-1)(\psi-1)}\right) \\ &= \frac{1}{\sqrt{5}}\left(\frac{(\phi^{n+1}-1)(-\phi)- (\psi^{n+1}-1)(-\psi)}{-1}\right) \\ &= \frac{1}{\sqrt{5}}\left((\phi^{n+1}-1)\phi- (\psi^{n+1}-1)\psi \right) \\ &= \frac{1}{\sqrt{5}}\left(\phi^{n+2}-\phi- \psi^{n+2}+\psi \right) \\ &= \frac{1}{\sqrt{5}}\left(\phi^{n+2}-\psi^{n+2}-(\phi-\psi) \right) \\ &= \frac{1}{\sqrt{5}}\left(\phi^{n+2}-\psi^{n+2}-\sqrt{5}\right) \\ &= \frac{\phi^{n+2}-\psi^{n+2}}{\sqrt{5}}-1 \\ &= F_{n+2}-1. \end{array} \end{equation} and from this we get \begin{equation} \sum_{i=0}^n F_i = F_{n+2}-1. \end{equation} Notice also that $F_n=F_{n+1}-F_{n-1}$, for any integer $n$ greater than $0$. We could have used this simple property to expand the above sum into telescopic series and get the same result. Have we chosen to go this path we would have got \begin{equation} \begin{array}{ll} \sum_{i=0}^n F_i &= F_0 + (F_2- F_0)+( F_3-F_1)+ ( F_4- F_2)+(F_5- F_3) + \\ \; & \;\;\; \ldots + ( F_{n-1}- F_{n-3})+(F_n- F_{n-2}) +(F_{n+1}- F_{n-1}) \\ \ &= -F_1+F_n+F_{n+1} \\ \ &= F_{n+2}-1. \end{array} \end{equation} This video (by Mark Eichenlaub) contains a visualized form of this telescopic series. $\blacksquare$

A Fibonacci number is any given element in the Fibonacci sequence. Now, given a positive number $x$ how do we know whether $x$ is a Fibonacci number or not?

The equality $y^2-xy-x^2=\pm 1$ if $\{ F_n, F_{n+1} \} = \{x,y\}$.

We need to prove that for any $(x,y)$ in $A$ there exists nonnegative integer $n$ such that $F_n=x$ and $F_{n+1}=y$. Namely \begin{equation} \tag{6} \forall (x,y) \in A \big(\exists n \in \mathcal{N}_0( F_n=x \mbox{ and } F_{n+1}=y ) \big) \end{equation} We prove (6) by induction. The base case, where $(x,y)=(0,1)$ is easily verified (we get $F_0=x=0$ and $F_1=y=1$). Let $(a,b)$ be any member of $A$. Suppose (this is the induction assumption) that for (6) holds for any $(u,v)$ that is less than $(a,b)$. If we prove (6) for $(a,b)$, then (by the axiom of induction) we done. Consider the pair $(b-a,a)$. Clearly, $b-a$ is nonnegative integer and, of course, $a$ is positive integer. Since \begin{equation} \begin{array}{l} a^2-(b-a)a-(b-a)^2 &= a^2-ab+a^2-b^2+2ab-a^2 \\ &= -b^2+ab+a^2\\ &= -(b^2-ab-a^2) \\ &= -\pm 1 \\ &= \pm 1 \end{array} \end{equation} the pair $(b-a,a)$ is in $A$. Given the fact that $a < b $ we get $(b-a,a) < (a,b)$, thus using the induction assumption we may infer the existence of positive integer $k$ such that $b-a=F_k$ and $a=F_{k+1}$. But, \begin{equation} \begin{array}{l} b &=(b-a)+b \\ &=F_k+F_{k+1} \\ &=F_{k+2}, \end{array} \end{equation} hence, $a=F_{k+1}$ and $b=F_{n+1}$, and since $(a,b)\in A$, the pair $(a,b)$ satisfies formula (6). $\square$

Still we need to know how to determine whether a given number is a Fibonacci number or not?

- The number $x$ is even.
- The number $x$ is odd.

In the second case one can easily see that $x^2$ must be odd, therefore $5x^2\pm 4$ must be odd. This implies that $\sqrt{5x^2\pm 4}$ is odd, thus $x+\sqrt{5x^2\pm 4}$ is even, therefor the right side of equality (8) must be an integer, hence $y$ is an integer.

In any case we get that the integers $x$ and $y$ satisfy equality (1), hence we can use the Successive Fibonacci Number Test to deduce the existence of a natural number $n$ such that $x=F_n$ and $y=F_{n+1}$. Hence, $x$ is a Fibonacci number. $\blacksquare$