Fibonacci Sequence | a Pattern of Natural Beauty| Binet formula

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$.

Ted talk on the magic of Fibonacci numbers, by Prof. Arthur T. Benjamin

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

$$\tag{1} F_n=\frac{\phi^n-\psi^n}{\phi-\psi}$$

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.

Theorem $\frac{F_{n+1}}{F_n} = \phi$ Proof:

Multiplying $\phi$ and $\psi$ yields $\phi\psi=-1$ and from this we get

$\phi = -\psi^{-1}.$ Using the Binet formula we get $$\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}$$ Since $|\psi|<1$, we get $$\tag{3} \lim_{n\to\infty} \psi^n = 0.$$ Since $\phi > 1$, we get $$\tag{4} \lim_{n\to\infty} \phi^n = \infty.$$ From equalities (3) and (4) we get $$\lim_{n\to\infty}\frac{\psi^n+\psi^{n+2}}{\phi^n-\psi^n}=0.$$ The last equality and equality (2) implies that $$\lim_{n\to\infty}\frac{F_{n+1}}{F^n}=\phi.$$ $\blacksquare$

Consider the sum $$\sum_{i=0}^n F_i$$

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{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}$$ and from this we get $$\sum_{i=0}^n F_i = F_{n+2}-1.$$ 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{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}$$ 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 $$\tag{5} y^2-xy-x^2=\pm 1.$$ 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 $$\tag{6} \forall (x,y) \in A \big(\exists n \in \mathcal{N}_0( F_n=x \mbox{ and } F_{n+1}=y ) \big)$$ 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{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}$$ 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{array}{l} b &=(b-a)+b \\ &=F_k+F_{k+1} \\ &=F_{k+2}, \end{array}$$ 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{array}{l} \psi\phi=-1 \\ \phi+\psi=1 \\ \phi^2=\phi+1 \quad \mbox{and} \quad \psi^2=\psi+1 \end{array}$$ Using these equalities and Binet formula, we get $$\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}$$ $\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 $$y^2-xy-x^2=\pm 1 \tag{7}$$ 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 $$y=\frac{1}{2}\left( x+\sqrt{5x^2\pm 4} \right). \tag{8}$$

$\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:
1. The number $x$ is even.
2. The number $x$ is odd.
In the first case we can see that $x^2$ is even, hence $5x^2\pm 4$ is even. This implies that $\sqrt{5x^2\pm 4}$ is even. The sum of two even numbers must be even, therefor $x+\sqrt{ 5x^2\pm 4}$ is even. This implies that the right side of equality (8) is an integer, thus $y$ is an integer.
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$

Tags Math