Two Fascinating Properties of the Fibonacci Sequence

There is no better way to learn mathematical induction than to work with the Fibonacci sequence

The Fibonacci sequence is a very well known and studied sequence of numbers which is often used in schools and in recreational mathematics because it can easily be understood by those with a limited technical mathematics education. The sequence is defined as follows: the first term is zero, the second term is one, and any other term is the sum of the prior two terms in the sequence. The sequence is written formally as follows:

for n > 1. The first ten terms of the sequence are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.

There is plenty of evidence that these numbers were known over 2000 years ago as part of the Sanskrit poetic tradition. In Europe, the sequence first appeared in Fibonacci’s book Liber Abaci in 1202, where he used it to model a population of rabbits. Nowadays, the sequence has applications in many fields including economics, optics and financial market trading.

Page from Liber Abaci (1202) showing the Fibonacci sequence in the right margin

The Fibonacci numbers have a lot of interesting and surprising properties, two of which I will illustrate and prove here. Both proofs will use mathematical induction.

1. Mathematical induction

If you are not familiar with mathematical induction, think about it like this. Imagine that I have a never-ending set of dominoes and I am going to stand them all up on their edges to form a chain of dominoes that will knock each other over forever. To be sure this happens, I need to know the following:

1. That the first domino gets knocked over.
2. That any domino that gets knocked over will cause the next domino to get knocked over.

In a similar way, we can prove that something is true for all numbers n by proving that:

1. It is true for n = 1 (called the induction start)
2. If it is true for n = k then it is true for n = k + 1. (This is called the induction step. A variant on this is strong induction…