Introduction
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$.
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'':
Binet Formula
\begin{equation} \tag{1} F_n=\frac{\phi^n-\psi^n}{\phi-\psi} \end{equation}Proof:
It is fairly easy to prove the Binet formula by using mathematical induction. The base case
\[ F_0=\frac{\phi^0-\psi^0}{\phi-\psi} \] is readily verified.Inductive Step:: Suppose that the Binet formula holds for integer $m$.
Notice that both $\psi$ and $\phi$ satisfy $x^2-x-1=0$. Thus,
$\phi^2= \phi+1$ and $\psi^2=\psi+1$. Using these two equalities we get \[ \begin{array}{l} \frac{\phi^{m+1}-\psi^{m+1}}{\phi-\psi} &= \frac{\phi^{m-1}\phi^2-\psi^{m-1}\psi^2}{\phi-\psi} \\ &= \frac{\phi^{m-1}(\phi+1)-\psi^{m-1}(\psi+1)}{\phi-\psi} \\ &= \frac{\phi^m-\psi^m}{\phi-\psi}+\frac{\phi^{m-1}-\psi^{m-1}}{\phi-\psi} \\ &= F_m+F_{m-1} \\ &= F_{m+1} \end{array} \] $\blacksquare$
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.
Multiplying $\phi$ and $\psi$ yields $\phi\psi=-1$ and from this we get
\[ \phi = -\psi^{-1}. \] Using the Binet formula we get \begin{equation} \begin{array}{l} \tag{2} \frac{F_{n+1}}{F_n} &= \frac{\phi^{n+1}-\psi^{n+1}}{\phi^n-\psi^n} \\ &=\phi \left( \frac{\phi^n}{\phi^n-\psi^n} + \frac{\psi^{n+2}}{\phi^n-\psi^n}\right) \\ &=\phi \left( \frac{\phi^n-\psi^n}{\phi^n-\psi^n} + \frac{\psi^n+\psi^{n+2}}{\phi^n-\psi^n}\right) \\ &=\phi \left(1 + \frac{\psi^n+\psi^{n+2}}{\phi^n-\psi^n}\right) \end{array} \end{equation} Since $|\psi|<1$, we get \begin{equation} \tag{3} \lim_{n\to\infty} \psi^n = 0. \end{equation} Since $\phi > 1 $, we get \begin{equation} \tag{4} \lim_{n\to\infty} \phi^n = \infty. \end{equation} From equalities (3) and (4) we get \begin{equation} \lim_{n\to\infty}\frac{\psi^n+\psi^{n+2}}{\phi^n-\psi^n}=0. \end{equation} The last equality and equality (2) implies that \begin{equation} \lim_{n\to\infty}\frac{F_{n+1}}{F^n}=\phi. \end{equation} $\blacksquare$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?
Theorem 1 (Successive Fibonacci Number Test)
Let $F_n$ be a Fibonacci sequence, let $x$ be any nonnegative integer and let
$y$ be any positive integer.
The equality $y^2-xy-x^2=\pm 1$ if $\{ F_n, F_{n+1} \} = \{x,y\}$.
Proof:
Without loosing generality, we assume that $F_n=x$ and let $F_{n+1}=y$, in the right part or the above if statement.
$\Rightarrow$
Let us denote \begin{equation} \tag{5} y^2-xy-x^2=\pm 1. \end{equation} Now, given equality (5) we need to prove that $F_n=x$ and $F_{n+1}=y$. If $x>y$, then \[ y^2-xy-x^2 < y^2-y^2-y^2 = -y^2 < -1 \] and this contradict equality (5), thus $x\le y$. In addition if $x\ge 1$, then $y\ge 1$. Let us denote the set of all positive integers with $\mathcal{N}^{+}$ and the set of all nonnegative integers with $\mathcal{N}_0$. Now, consider the following set \[ A = \Big\{(x,y)\;\Big|\; y^2-xy-x^2=\pm 1, \mbox{ where } x\in \mathcal{N}_0 \mbox{ and } y \in \mathcal{N}^{+} \Big\}. \] Define \[ (x_0,y_0) < (x_1,y_1) \Longleftrightarrow y_0 < y_1 \] for any $(x_0,y_0)$ and $(x_1,y_1)$ in $A$.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$
$\Leftarrow$
Let us denote $x=F_n$ and $y=F_{n+1}$. It be easily verified that \begin{equation} \begin{array}{l} \psi\phi=-1 \\ \phi+\psi=1 \\ \phi^2=\phi+1 \quad \mbox{and} \quad \psi^2=\psi+1 \end{array} \end{equation} Using these equalities and Binet formula, we get \begin{equation} \begin{array}{ll} y^2-xy-x^2 &=& (F_{n+1})^2-F_nF_{n+1}-(F_n)^2 \\ &=& \frac{\left(\phi^{n+1}-\psi^{n+1}\right)^2}{5}- \frac{\left(\phi^n-\psi^n\right)\left(\phi^{n+1}-\psi^{n+1}\right)}{5}-\frac{\left(\phi_n-\psi_n\right)^2}{5} \\ &=& \frac{1}{5}\Big(\phi^{2n}(\phi+1)-2(\phi\psi)^{n+1}+\psi^{2n}(\psi+1)-\phi^{2n+1}-\\ &=& \psi^{2n+1}+ \phi^n\psi^{n+1}+\psi^n\phi^{n+1}-\phi^{2n}+2\phi^n\psi^n-\psi^{2n}\Big) \\ &=& \frac{1}{5}\Big(\phi^{2n+1}+\phi^{2n}+2\cdot(-1)^n+\psi^{2n+1}+\psi^{2n}-\\ &=& \phi^{2n+1}-\psi^{2n+1}+ (-1)^n\psi+(-1)^n\phi-\phi^{2n}+2(-1)^n-\psi^{2n}\Big) \\ &=& \frac{1}{5}\left(2\cdot (-1)^n+ (-1)^n(\psi+\phi)+2(-1)^n\right) \\ &=& \frac{1}{5}\left(2\cdot (-1)^n+ (-1)^n+2(-1)^n\right) \\ &=& \frac{1}{5}\left(5\cdot (-1)^n\right) \\ &=& (-1)^n \\ &=& \pm 1 \\ \end{array} \end{equation} $\blacksquare$Still we need to know how to determine whether a given number is a Fibonacci number or not?
Theorem 2 (Fibonacci Number Test)
Let $x$ be any positive integer. $x$ is a Fibonacci number if either one of $5x^2+4$ or $5x^2-4$ is a perfect square.Proof:
Recall that any integer $q$ is a perfect square if both $q$ and $\sqrt{q}$ are integers. From the equation \begin{equation} y^2-xy-x^2=\pm 1 \tag{7} \end{equation} we get \[ y=\frac{x\pm \sqrt{x^2+4(x^2\pm 1)}}{2} \] Since we need the positive part of $y$, we may write the last equality in the following form \begin{equation} y=\frac{1}{2}\left( x+\sqrt{5x^2\pm 4} \right). \tag{8} \end{equation}$\Rightarrow$
Since $x$ is a Fibonacci number, there must be nonegative integer $n$ such that $x=F_n$. We can thus use the Successive Fibonacci Number Test to conclude that $y=F_{n+1}$ is a solution to equality (7). Hence the right part of equality (8) is a Fibonacci number and this implies that $\sqrt{5x^2\pm 4}$ is an integer.$\Leftarrow$
Since $5x^2\pm 4$ is a perfect square, $\sqrt{5x^2\pm 4}$ is an integer. We know that $x$ is any integer, hence only one of the following cases hold:- 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$