## Finding Fibonacci, by Keith Devlin – a review

This book was sent to me by the publisher as a review copy.

I have a terrible admission to make. I came to this book with a paltry knowledge of Fibonacci (Leonardo of Pisa). The knowledge that I thought that I had was quickly shown in fact to be incorrect, so I was largely starting with a blank slate (Fibonacci did not discover the Fibonacci sequence, nor would he be terribly happy to know that in the popular psyche, this is what he is famous for).

In fact, this book is not really about Fibonacci (Devlin has another book about him). This is a book about the writing of a book, and about Devlin’s process of uncovering the history and importance of what Fibonacci had accomplished. It is a book about the research of the history of mathematics, and as such, it is a lovely tale: one of fortuitous moments of discovery, and of frustrations of searching for manuscripts.…

## Fibonacci and the Golden Ratio

The Fibonacci numbers $1, \ 1, \ 2,\ 3, \ 5,\ 8, 13,\ 21,\ 34, \ 55,\ 89,\ 144, \ \cdots$ are defined by the recurrence relation

$F_1 = F_2 = 1, \ F_{n+2} = F_{n+1} + F_n \ \textrm{ for } n \ge 1.$

Consider now the ratios $\dfrac{F_{n+1}}{F_n}$:

$\dfrac 11, \ \dfrac 21, \ \dfrac 32, \ \dfrac 53, \ \dfrac 85, \ \dfrac {13}8, \dfrac {21}{13}, \ \dfrac {21}{13}, \ \dfrac {34}{21}, \dfrac {55}{34}, \dfrac {89}{55}, \ \dfrac {144}{89}, \ \cdots \ .$

The sequence of fractions appears to rise and fall alternately. This observation can be confirmed by reference to the equation

$F_{n+1}^2 - F_nF_{n+2} = (-1)^n$

which, when divided by $F_{n+1}F_n$ gives

$\dfrac{F_{n+1}}{F_n} - \dfrac {F_{n+2}}{F_{n+1}} = \dfrac {(-1)^n}{F_{n+1}F_n } \ ,$

showing that the difference between successive terms in the sequence of ratios is alternately positive and negative.

Calculating the first few terms suggest that successive ratios converge to 1.618 … . This may be established by using Binet’s formula (see the previous post):

$F_n = \dfrac 1{\sqrt 5}\Big(\Big(\dfrac{1+\sqrt 5}2 \Big)^n - \Big(\dfrac{1-\sqrt 5}2 \Big)^n\Big) \$

from which we have

$\dfrac {F_{n+1}}{F_n} = \dfrac {\Big(\dfrac{1+\sqrt 5}2 \Big)^{n+1} - \Big(\dfrac{1-\sqrt 5}2 \Big)^{n+1}} {\Big(\dfrac{1+\sqrt 5}2 \Big)^n - \Big(\dfrac{1-\sqrt 5}2 \Big)^n}$

Now look at the second terms in the numerator and denominator.

Since

$-1< \dfrac{1-\sqrt 5}2 < 1$,

these terms tend to zero as $n$ tends to infinity, so are insignificant in comparison with the first terms. It follows that

$\frac {F_{n+1}}{F_n} \rightarrow \frac{1+\sqrt 5}2 \ \ - \ \ \textrm{the Golden Ratio}.$

Check out the link between the golden spiral and the Fibonacci sequence here.

————

Originally by John Webb

 How clear is this post?

## Fibonacci and Binet

The Fibonacci numbers $1, \ 1, \ 2,\ 3, \ 5,\ 8, 13,\ 21,\ 34, \ 55,\ 89,\ 144, \ \cdots$

are defined by a recurrence relation

$F_1 = F_2 = 1, \ F_{n+2} = F_{n+1} + F_n \ \textrm{ for } n \ge 1.$

This definition allows one to find any Fibonacci number, but for large values of $n$ it would be time-consuming to compute $F_n$ this way. Worse, any error of calculating a term would be repeated and magnified in every subsequent term. So a natural question to ask is whether there is a simple formula, in terms of $n$, which enables one to calculate $F_n$ without having to find all the earlier Fibonacci numbers.

In 1843 the French mathematician Jacques Philippe Marie Binet announced that he had found a Fibonacci Formula. Although it was later revealed that other mathematicians, including Leonhard Euler and Abraham de Moivre, had worked out the same formula a hundred years earlier, the formula is today still labelled Binet’s Formula.

Deriving the Binet’s formula starts with a simple little quadratic equation $x^2 = x + 1.$

Multiplying the equation by successive powers of $x$, and simplifying at each step, gives

$x^3 = x(x^2) = x(x+1) = x^2 + x = (x+1) + x = 2x + 1$

$x^4 = x(x^3) = x(2x+1) = 2x^2 + x = 2(x+1) + x = 3x+2$

$x^5 = x(x^4) = x(3x+2) = 3x^2 + 2x = 3(x+1) + 2x = 5x + 3$

$x^6 = x(x^5) = x(5x+3) = 5x^2 + 3x = 5(x+1) + 3x = 8x + 5$

and so on.…

## Fibonacci and induction

The Fibonacci numbers $F_n$ are defined by: $F_1 = F_2 = 1$, $F_{n+2} = F_{n+1} + F_n \textrm{ for } n\ge 1.$

The numbers are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, …

The Fibonacci numbers have many interesting properties, and the proofs of these properties provide excellent examples of Proof by Mathematical Induction. Here are two examples. The first is quite easy, while the second is more challenging.

Theorem

Every fifth Fibonacci number is divisible by 5.

Proof

We note first that $F_5 = 5$ is certainly divisible by 5, as are $F_{10} = 55$ and $F_{15} = 610.$ How can we be sure that the pattern continues?

We shall show that: IF the statement “$F_n$ is divisible by 5″ is true for some natural number $m$, THEN the statement is also true for the natural number $m+5$.

Now

$F_{m+5} = F_{m+4} + F_{m+3}$

$= (F_{m+3} + F_{m+2}) + F_{m+3}$

$= 2F_{m+3} + F_{m+2}$

$= 2(F_{m+2} + F_{m+1}) + (F_{m+1} + F_m)$

$= 2F_{m+2} + 3F_{m+1} + F_m$

$= 2(F_{m+1} + F_m) +3F_{m+1} + F_m$

$= 5F_{m+1} + 3F_m$.

Since we know that $F_m$ is divisible by 5, it is now clear that $F_{m+5}$ is also divisible by 5.…