# Fibonacci Numbers and the Euler-Binet Formula

• By David A. Smith, Founder & CEO, Direct Knowledge
• David Smith has a B.S. and M.S. in Mathematics and has enjoyed teaching calculus, linear algebra, and number theory at both Tarrant County College and the University of Texas at Arlington. David is the Founder and current CEO of Direct Knowledge.

We study the Fibonacci numbers and show how to use mathematical induction to prove several Fibonacci identities. We also develop the Euler-Binet Formula involving the golden-ratio. The Fibonacci Prime Conjecture and the growth of the Fibonacci sequence is also discussed.

After having studied mathematical induction, the Fibonacci numbers are a good subject to test ones abilities to perform induction. There are two obvious reasons for this. Firstly, many of the results exercises are relatively straight-forward. Secondly, many of the results obtained are quite surprising. For instance, the sum of the squares of the first $n+1$ Fibonacci numbers is the same as the product of the $n$-th and the $n+1$-th. This fact is easily provable by mathematical induction. We now study the Fibonacci Numbers and the Euler-Binet Formula.

## Introduction to the Fibonacci Numbers

Fibonacci numbers are defined as a recursive sequence by starting with 0 and 1, and then adding the previous two integers together. It has long been noticed that the Fibonacci numbers arise in many places throughout the natural world. Fibonacci numbers have many special mathematical properties.

DefinitionFibonacci numbers are the positive integers defined by $$f_0=0, \quad f_1=1, \quad f_{n}=f_{n-1}+f_{n-2}$$ for $n\geq 2$.

The first 21 Fibonacci numbers are \begin{equation*}\begin{matrix} 1 & 1 & 2 & 3 & 5 & 8 & 13 \\ 21 & 34 & 55 & 89 & 144 & 233 & 377 \\ 610 & 987 &1597 &2584 &4181 & 6765 & 10946 \end{matrix} \end{equation*}

## Fibonacci Identities

Here we prove several identities involving Fibonacci numbers. The idea is to provide several interesting examples on how mathematical induction can be applied to give rigorous arguments on (perhaps) experimentally found identities.

Example. Prove that for all positive integers $n$, $$\sum_{i=0}^n f_{i}^2 = f_n f_{n+1}.$$

Solution. Let $P$ be the set of positive integers for which the equation is true. It follows that $0\in P$, since $f_0^2 =0=f_0 f_1$. Now we assume $k\in P$. It then follows $k+1\in P$ by \begin{align*} \sum_{i=0}^{k+1} f_i^2  & =\sum_{i=0}^{k} f_i^2+ f_{k+1}^2 \\ & =f_k f_{k+1}+f_{k+1}^2 \\ & =f_{k+1}(f_k+f_{k+1}) =f_{k+1} f_{k+2}. \end{align*} By mathematical induction $P=\mathbb{N}$ as desired.

Example. Prove that for all positive integers $n$, $$\sum _{j=1}^n f_{2j}=f_{2n+1}-1.$$

Solution. For $n=1,$ $f_2=1= f_3-1$ so the base case holds.  Assume, for some positive integer $k$, that the equation holds.  Then we find \begin{align*} \sum _{j=1}^{k+1} f_{2j} & =\sum _{j=1}^k f_{2j}+f_{2k+2} \\ & =f_{2k+1}-1+f_{2k+2} \\ & =f_{2k+3}-1. \end{align*} By mathematical induction, the equation holds for all positive integers $n$.

## More Examples on Fibonacci Numbers

To develop a better understanding of the unique behaviors of Fibonacci numbers, here are a few more examples.

Example. Prove that for all positive integers $n$,  $$\sum_{i=1}^n f_{2i-1} = f_{2n}.$$

Solution. Since $f_1=1=f_2$ we see the base case holds. Assume, for some positive integer $k$, that the equation holds. Then we find\begin{align*} \sum_{i=1}^{k+1} f_{2i-1} & =\sum_{i=1}^k f_{2i-1} +f_{2(k+1)-1} \\ & =f_{2k}+f_{2k+1} \\ & =f_{2k+2} \\ & =f_{2(k+1)}. \end{align*} By mathematical induction, the equation holds for all positive integers $n$.

Example. Prove that for all positive integers $n,$ $$\sum _{i=1}^n f_i = f_{n+2}-1.$$

Solution. For $n=1,$ $f_1=1=f_3-1$ so the bases case holds. Assume, for some positive integer $k$, that the equation holds. Then we find \begin{align*} \sum _{j=1}^{k+1} f_j & =\sum _{j=1}^k f_j+f_{k+1} \\ & =f_{k+2}-1+f_{k+1} \\ & =f_{k+1}+f_{k+2}-1 \\ & =f_{k+3}-1. \end{align*} By mathematical induction, the equation holds for all positive integers $n$.

Example. Prove that for all positive integers $n,$ $$\label{fifthfib} f_{n+1} f_{n-1} – \left(f_n\right)^2 = (-1)^n.$$

Solution. For $n=1,$ $f_2 f_0 -\left(f_1\right)^2=(-1)^1$ so the base case holds. Assume, for some positive integer $k$, that \eqref{fifthfib} holds. Then we find \begin{align*} f_{k+2}f_k-\left(f_{k+1}\right)^2 & = \left(f_{k+1}+f_k\right)f_k-\left(f_{k+1}\right)\left(f_{k-1}+f_k\right) \\ & =f_{k+1}f_k+\left(f_k\right){}^2-f_{k+1}f_{k-1}-f_{k+1}f_k \\ &=(-1)\left(-\left(f_k\right){}^2+f_{k+1}f_{k-1}\right) \\ & =(-1)(-1)^k =(-1)^{k+1}. \end{align*} By mathematical induction, the equation holds for all positive integers $n$.

## The Euler-Binet Formula

Firstly, we notice that the Euler-Binet formula gives us a closed form for calculating the $n$-th Fibonacci number. In fact, the formula is in terms of the golden ratio $\phi$. To prove the formula we first need the following lemma involving the golden ratio.

Lemma. For any solution $x$ of $x^2-x-1=0$ and any positive integer $n$, $$x^n=x \, f_n+f_{n-1}.$$

Proof. The proof is by induction. Clearly, $x^1= x \, f_1 + f_{0} = x (1) + 0 = x$ so the base case holds. Assume now that, for some positive integer $k$, that $$x^k=x \, f_k+f_{k-1}$$ We wish to prove that $x^{k+1}=x\, f_{k+1}+f_{k}$. To this end, multiply the identity by $x$ to obtain \begin{align*} x^{k+1} = x^2 \, f_k+ x, f_{k-1} & = (x+1) \, f_k + x \, f_{k-1} \\ & = x\, (f_k + f_{k-1}) + f_k \\ & =x \, f_{k+1} + f_k \end{align*} as needed.

The golden ratio is the positive root of the quadratic equation $x^2-x-1=0$, that is, $$\phi = \frac{1+\sqrt{5}}{2}.$$ The conjugate of $\phi$ is denoted by $$\tau = \frac{1-\sqrt{5}}{2}.$$  It is easily verified that $\phi\tau=-1$ and $\phi-\tau=\sqrt{5}$. We now give the closed formula to compute the $n$-th Fibonacci number. The golden ratio and the fibonacci sequence are inextricably linked by the Euler-Binet Formula.

Theorem. (Euler-Binet Formula) For all positive integers $n$, $$f_n=\frac{1}{\sqrt{5}}\left(\phi^n-\tau^n\right).$$

Proof. From above, we have $$\phi^n = \phi \, f_n + f_{n-1}\quad \text{ and } \quad \tau^n = \tau \, f_n + f_{n-1}.$$ It follows that $f_n=\frac{\phi^n-\tau^n}{\phi-\tau}$. Now observe that the Euler-Binet Formula follows since $\phi-\tau=\sqrt{5}$.

## The Fibonacci Prime Conjecture

Leonardo Pisano Bigollo (1170 — 1250) was also known simply as Fibonacci. He used the number sequence in his book called Liber Abaci (Book of Calculation). Fibonacci did not discover the sequence but used it as an example in Liber Abaci.

Here are a few more Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811.

In other words, this leads us to ask, how many of these Fibonacci numbers are prime?

A Fibonacci prime is a number in the Fibonacci sequence that is a prime.  For instance, the first seven Fibonacci primes are 2, 3, 5, 13, 89, 233, 1597.  Fibonacci primes with thousands of digits have been found. In addition, here is a large (29 digit) Fibonacci number: $$19,134,702,400,093,278,081,449,423,917.$$ While it remains whether Fibonacci primes are infinite, the conjecture is that there are infinitely many Fibonacci prime numbers

## The Growth of the Fibonacci Sequence

Firstly, we notice that the Fibonacci numbers grow exponentially fast. Secondly, we can understand the growth rate in terms of the golden ratio.

Example. Show that $f_n > \left(\frac{3}{2}\right)^{n-1}$ whenever $n$ is a positive integer greater than 6.

Solution. We verify that $$f_6=8>\left(\frac{3}{2}\right)^5\approx 7.59375.$$ We also must verify $$f_7=13>\left(\frac{3}{2}\right)^6\approx 11.390625.$$ Now let $k>7$, and assume the inductive hypothesis that $f_i >(3/2)^{i-1}$ for $i=k-1$ and $i=k-2$. Then we have \begin{align*} f_k = \ & f_{k-1}+f_{k-2} \\ & > \left(\frac{3}{2}\right)^{k-2}+\left(\frac{3}{2}\right)^{k-3}  \\ & =\left(\frac{3}{2}\right)^{k-3}\left(\frac{3}{2}+1\right)\\ & = \left(\frac{3}{2}\right)^{k-3}\left(\frac{5}{2}\right) \\ & >\left(\frac{3}{2}\right)^{k-3}\left(\frac{9}{4}\right) \\ & =\left(\frac{3}{2}\right)^{k-3}\left(\frac{3}{2}\right)^2 \\ & =\left(\frac{3}{2}\right)^{k-1} \end{align*} as desired.

The golden ratio $\phi$ is approximately, 1.61803398875. We can use the golden ratio to improve our understanding of the growth rate of the Fibonacci sequence.

Example. Show that $f_n > \phi^{n-2}$ whenever $n$ is a positive integer greater than 3.

Solution. We verify that $$f_3=3>\phi^1\approx 1.618\qquad \text{and}\qquad f_4=5>\phi^2\approx 2.618.$$ Now let $k>4$, and so assume the inductive hypothesis that $f_i >(3/2)^{i-1}$ for $i=k-1$ and $i=k-2$. Now using $\phi^2=\phi+1$ we have \begin{align*} f_k & =f_{k-1}+f_{k-2} >\phi^{k-3}+\phi^{k-4} \\ & =\phi^{k-4}\left(\phi+1\right) \\ & =\phi^{k-4}\phi^2 \\ & =\phi^{k-2} \end{align*} as desired.

## Exercises on the Fibonacci Numbers

Exercise. Find the Fibonacci numbers $f_{24}$,  $f_{32}$, and  $f_{44}$.

Exercise.  Write out the first 50 Fibonacci numbers.

Exercise. Show that $f_{n+3}+f_n=2f_{n+2}$ whenever $n$ is a positive integer.

Exercise.  Show that $f_{n+3}-f_n=2f_{n+1}$ whenever $n$ is a positive integer.

Exercise. Show that $f_{n-2}+f_{n+2}=3f_n$ whenever $n$ is a positive integer with $n\geq 2.$

Exercise. Show that $f_{2n}=f_{n}^2+2f_{n-1}f_n$ whenever $n$ is a positive integer with $n\geq 2.$

Exercise. Show that $f_{2n+1}=f_{n+1}^2+f_{n}^2$ whenever $n$ is a positive integer.

Exercise.  Show that $f_{2n}=f_{n+1}^2-f_{n-1}^2$ whenever $n$ is a positive integer.

Exercise. Show that for all positive integers $n,$  $$f_1f_2 + \left(f_2f_3+f_3f_4\right)\cdots +\left(f_{2n-2}f_{2n-1}+f_{2n-1}f_{2n}\right)=\left(f_{2n}\right)^2.$$

Exercise. Show that $f_{n+2}^2-f_{n+1}^2=f_n f_{n+3},$ whenever $n$ is a positive integer greater than 1.

## More Exercises on the Fibonacci Numbers

You may also attempt to solve the following exercises. Note that we have also introduced Lucas numbers in this section, so feel free to look it up.

Exercise. Show that $f_{n+1}f_n-f_{n-1}f_{n-2}=f_{2n-1}$ whenever $n$ is a positive integer greater than 2.

Exercise. Show that $f_1 f_2+f_2f_3+\cdots +f_{2n-1}f_{2n}=f_{2n}^2$ whenever $n$ is a positive integer.

Exercise. Prove that $f_{m+n}=f_m f_{n+1}+f_n f_{m-1}$ whenever $n$ is a positive integer.

Exercise. Prove that $f_n > \left(\frac{5}{3}\right)^{n-1}$, for all $n\geq 2$.

Exercise. Show that for $n\geq 2$, $$f_n=\frac{f_{n-1}+\sqrt{5 f_{n-1}^2+4(-1)^n}}{2}.$$ Notice that this formula gives $f_n$ in terms of one predecessor rather than two predecessors.

Exercise. Let $F=\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}$. Show that $$F^n=\begin{bmatrix}f_{n+1} & f_n \\ f_n & f_{n-1}\end{bmatrix}$$ for all $n\geq 1$.

Exercise. Let $a_0=1$ and, for $n>0$, let $a_n=2 a_{n-1}+1$. The first few terms of the sequence are 1,3,7,15. What are the next fews terms?  Prove that $a_n=2^{n+1}-1$ for all positive integers.

Exercise.  Let $b_0=1$ and, for $n>0$, let $b_n=3 b_{n-1}-1$. Find the first five terms of the sequence. Then prove that $b_n=(3^{n}+1)/2$ for all positive integers.

## Additional Exercises on the Fibonacci Numbers

Exercise. Find the first 50 Lucas numbers

Exercise. Find and prove a formula for the sum of the first $n$ Lucas numbers when $n$ is a positive integer.

Exercise. Find and prove a formula for the sum of the first $n$ Lucas numbers with odd indices when $n$ is a positive integer.

Exercise. Find and prove a formula for the sum of the first $n$ Lucas numbers with even indices when $n$ is a positive integer.

Exercise. Show that $f_{2n}=f_n L_n$ whenever $n$ is a positive integer.

Exercise. Prove that $L_{m+n}=f_{m+1}L_n+f_mL_{n-1}$ whenever $m$ and $n$ are positive integers with $n >1$.

Exercise. Prove that $L_n=\phi^n+\tau^n$ where $\phi$ is the golden ratio and $\tau$ its conjugate.

Exercise. Establish each of the following for all $n\in \mathbb{N}$.

$(1) \quad L_n-5 f_n^2=4(-1)^n$

$(2) \quad L_{2n}=L_n^2-2(-1)^n$

$(3) \quad f_{n+1}+f_{n-1}=L_n$

$(4) \quad L_{n+1}+L_{n-1}=5 f_n$

$(5) \quad L_{2n+1}=L_n L_{n+1}-(-1^n)$

$(6) \quad L_{n-1}L_{n+1}-L_n^2=5(-1)^{n-1}$, $n\geq 2$