Introducing the Fibonacci Sequence

We’ve been examining inductive proof in preparation for the Fibonacci sequence, which is a playground for induction. Here we’ll introduce the sequence, and then prove the formula for the nth term using two different methods, using induction in a way we haven’t seen before.

The basics: raising rabbits

We can start with a basic question from 2001:

Fibonacci Sequence

I need help understanding what the Fibonacci sequence really is. I have visited many different Web sites, but they have the same information.

Doctor Jodi answered, though possibly offering the same information as elsewhere:

Hi Brandi,

The Fibonacci sequence is a sequence of numbers. Specifically, the sequence

   1, 1, 2, 3, 5, 8, 13, 21, ... 

How do you get the next term in the sequence? (You add the two previous terms.)

Stated formally, we define the sequence recursively, meaning that each term is calculated from the previous term(s). Starting with \(F_1=1\) and \(F_2=1\), we then define each succeeding term as the sum of the two before it: \(F_{n+1} = F_n+F_{n-1}\): $$F_1=1\\F_2=1\\F_3=F_2+F_1=1+1=2\\F_4=F_3+F_2=2+1=3\\F_5=F_4+F_3=3+2=5$$

The Fibonacci sequence is named for Leonardo Pisano (his nickname was Fibonacci), an Italian educated in North Africa who lived around 1200 A.D. This famous sequence arose in connection with the following problem, taken from a book Fibonacci published in 1202:

A certain man put a pair of rabbits in a place surrounded on all sides by a wall. How many pairs of rabbits can be produced from that pair in a year if it is supposed that every month each pair begets a new pair which from the second month on becomes productive? 

You can read more about Fibonacci's life from the MacTutor History of Mathematics archive:

  https://mathshistory.st-andrews.ac.uk/Biographies/Fibonacci/

I find it interesting that the Fibonacci sequence is not something that its “creator” researched in detail (or perhaps even stated as a sequence at all!), but just an exercise intended to give practice in addition! But others later found it endlessly fascinating, as we’ll be seeing. (The book in which the problem is found, Liber Abbaci, or The Book of Calculation, introduced arithmetic with our modern numerals to a world built on Roman numerals and the abacus.)

For more about the history of the sequence (which was known before Fibonacci), see On the origin of the Fibonacci Sequence, by Scott and Marketos; among much more, this says:

Fibonacci himself does not seem to have associated that much importance to them; the rabbit problem seemed to be a minor exercise within his work. These numbers did not assume major importance and recognition until the 19th century thanks to the work of the French mathematician Edouard Lucas.

Here is Fibonacci’s problem (translated into English) and most of his solution, from Ron Knott’s site:

How Many Pairs of Rabbits Are Created by One Pair in One Year
A certain man had one pair of rabbits together in a certain enclosed place, and one wishes to know how many are created from the pair in one year when it is the nature of them in a single month to bear another pair, and in the second month those born to bear also.

Because the above written pair in the first month bore, you will double it; there will be two pairs in one month. One of these, namely the first, bears in the second month, and thus there are in the second month 3 pairs; of these in one month two are pregnant and in the third month 2 pairs of rabbits are born, and thus there are 5 pairs in the month;

… there will be 144 pairs in this [the tenth] month; to these are added again the 89 pairs that are born in the eleventh month; there will be 233 pairs in this month. To these are still added the 144 pairs that are born in the last month; there will be 377 pairs, and this many pairs are produced from the above written pair in the mentioned place at the end of the one year.

You can indeed see in the margin how we operated, namely that we added the first number to the second, namely the 1 to the 2, and the second to the third, and the third to the fourth and the fourth to the fifth, and thus one after another until we added the tenth to the eleventh, namely the 144 to the 233, and we had the above written sum of rabbits, namely 377, and thus you can in order find it for an unending number of months.

Margin:

beginning 1
first 2
second 3
third 5
fourth 8
fifth 13
sixth 21
seventh 34
eighth 55
ninth 89
tenth 144
eleventh 233
end 377

(Modern symbolism didn’t exist yet, so a few lines of arithmetic took paragraphs!)

Back to Doctor Jodi:

I recommend making a table depicting the first few months of the rabbits' lives. Mature rabbits (which will bear a new pair of rabbits in the next month) should be colored one color (say red), while the newborn rabbits should be colored another (say green). (There's a beautiful illustration like this in a book called the _Number Devil_ by Hans Magnus Enzensberger.)

Here is such a diagram, showing how the problem leads to the sequence:

We start with one new rabbit; each row has as many mature (red) rabbits as the total in the row before, plus as many new (green) rabbits as red rabbits in the row before, that is, the total of all rabbits in the row before that. We get 1, 1, 2, 3, 5, … as we expected. (I’ve shown only the female rabbits for simplicity.)

The problem, of course, is not at all realistic; like most elementary math exercises, it is highly simplified for the sake of making a workable problem, and like most interesting math problems, it is inspired by reality but takes on a life of its own.

The ratios of consecutive pairs of numbers in the Fibonacci sequence (1/1, 2/1, 3/2, 5/3, 8/5, etc.) tend to the Golden Ratio. 

You can find more responses to questions about the Fibonacci sequence and the Golden Ratio in the links to relevant sites on the Web in the Dr. Math FAQ:

  Golden Ratio, Fibonacci Sequence

We’ll be seeing the golden ratio (\(\phi\)) soon!

Ron Knott’s site, referred to above, is one source we have often sent students to. Its address in the FAQ is now a little wrong; the new address is

Fibonacci Numbers and the Golden Section

(The site says, “This site went live in March 1996 and is therefore the oldest maths site on the web!”; Ask Dr. Math started in 1994, but it was a different sort of math site.)

Deriving an explicit formula

But there’s more to say about what the Fibonacci sequence is! Here is a question from 1996:

Fibonacci sequence

What is the explicit formula for the Fibonacci numbers?   
 
Thank you very much for your help, 

Kate Bauer

What we have so far is called a recursive formula: \(F_{n+1} = F_n+F_{n-1}\). An explicit formula will directly tell us what the nth term is without having to calculate all the others – this is far beyond anything Fibonacci did. To get from one to the other requires some relatively advanced techniques. (Soon we’ll see how to prove this formula inductively, which as we’ve seen doesn’t provide a way to derive the formula without already knowing it. That’s why I’m showing this first.)

Doctor Charles answered:

There is an explicit formula for the Fibonacci numbers and it involves the Golden Mean (=phi=(1+sqrt(5))/2). However it is very ugly compared to the rest of the Fibonacci sequence's properties.

My definition of the sequence starts at 0 but you may prefer 1. 0 is easier to work with in this problem and it is easy to convert back at the end.

We have to solve:

  f_0 = 1
  f_1 = 1
  f_n = f_n-1 + f_n-2

This number \(\phi=\frac{1+\sqrt{5}}{2}\approx 1.618\) (Greek phi), also called the Golden Ratio, appears in many parts of math and even in the real world; we’ll examine that further in another post.

We usually take \(F_1=1, F_2=1\); this can be extended back to start with \(F_0=0,F_1=1\). Doctor Charles is changing the index so that his \(f_0\) is our \(F_1\); as a result, \(f_n=F_{n+1}\); but his final formula will be back in our form.

To solve difference equations like this (the technique is analogous to linear 2nd order differential equations) we first solve the auxiliary equation:

        k^2 = k + 1

and get   k = (1+sqrt(5))/2  or  (1-sqrt(5))/2
            =  phi           or  (1 - phi)

This gives that any sequence of the form 

        f_n = a * (phi)^n + b * (1-phi)^n

will satisfy the difference equation: 

        f_n = f_n-1 + f_n-2. 

You can check this by substituting the formula into the difference equation.

Thus far, we have found that any such sequence (whatever the initial two terms) can be written as \(f_n=a(\phi)^n+b(1-\phi)^n\). Here is the check he suggested: $$f_{n-1}=a(\phi)^{n-1}+b(1-\phi)^{n-1},f_{n-2}=a(\phi)^{n-2}+b(1-\phi)^{n-2}\\f_{n-1}+f_{n-2}=\left[a(\phi)^{n-1}+b(1-\phi)^{n-1}\right]+\left[a(\phi)^{n-2}+b(1-\phi)^{n-2}\right]\\=a(\phi)^{n-1}+a(\phi)^{n-2}+b(1-\phi)^{n-1}+b(1-\phi)^{n-2}\\=a(\phi+1)(\phi)^{n-2}+b\left((1-\phi)+1\right)(1-\phi)^{n-2}\\=a(\phi)^2(\phi)^{n-2}+b(1-\phi)^2(1-\phi)^{n-2}\\=a(\phi)^{n}+b(1-\phi)^{n}=f_n$$

We used the fact that \(\phi^2=\phi+1\) and \((1-\phi)^2=(1-\phi)+1\), since they are both solutions of the equation \(x^2=x+1\).

But we want a specific sequence:

Now we just have to find a and b such that f_0 = 1 and f_1 = 1.

   f_0 = 1 = a + b
   f_1 = 1 = a * phi + b * (1 - phi).

So we get  b (2*phi - 1) = phi - 1
   and     a (2*phi - 1) = phi.

but 2*phi - 1 = sqrt 5
so we have 

   f_n = phi/sqrt(5) * (phi)^n + (phi-1)/sqrt5 * (1-phi)^n

       = phi^(n+1) / sqrt(5)   - (1-phi)^(n+1) / sqrt(5)

and if you want your sequence to start at 0, not 1, you get the simpler:

   f_n = phi^n / sqrt(5) - (1-phi)^n / sqrt(5)

This can be written as $$F_n=\frac{\phi^n-(1-\phi)^n}{\sqrt{5}}$$ And since \(\phi^2=\phi+1\), $$1-\phi=\frac{\phi-\phi^2}{\phi}=\frac{-1}{\phi}$$ so we can also write it as $$F_n=\frac{\phi^n-(-\phi)^{-n}}{\sqrt{5}}$$

One implication of this formula is that the ratio of successive terms is $$\frac{F_{n+1}}{F_n}=\frac{\phi^{n+1}-(-\phi)^{-n-1}}{\phi^n-(-\phi)^{-n}}\rightarrow \frac{\phi^{n+1}}{\phi^n}=\phi$$ This is the fact, mentioned earlier, that the ratio of Fibonacci numbers approaches \(\phi\): $$1/1=1\\2/1=2\\3/2=1.5\\5/3=1.666…\\8/5=1.4\\13/8=1.625\\21/13=1.615…\\34/21=1.619…\\55/34=1.617…\dots\\89/55=1.618…$$

Proving it by induction: overview

Here is a question from 2001:

Binet's Formula and Induction

Everywhere I look everyone keeps saying that Binet's formula can be solved by induction. But what is induction, and can you prove Binet's formula by induction?

The explicit formula we just saw is commonly called Binet’s Formula, named for a mathematician who was not the first to discover it.

Doctor Rob answered, first introducing the concept of induction:

Thanks for writing to Ask Dr. Math, JT.

The Principle of Mathematical Induction states that if a certain statement that depends on n is true for n = 0, and if its truth for n = k implies its truth for n = k+1, then the statement is true for all integers n >= 0.

There is an equivalent form, which appears superficially to be different. It states that if a certain statement that depends on n is true for n = 0, and if its truth for all n <= k implies its truth for n = k+1, then the statement is true for all integers n >= 0.

To apply this Principle in either form is to prove the statement "by induction."

These two forms are called Weak Induction and Strong Induction, as we’ve seen previously. We’ll need the latter here.

Binet's formula is

   F(n) = (a^n-b^n)/(a-b).

Here F(n) is the nth Fibonacci number, defined by

   F(0) = 0,
   F(1) = 1,
   F(n) = F(n-1) + F(n-2), for all n >= 2.

The quantities a and b are defined by the formulas

   a = (1+sqrt[5])/2,
   b = (1-sqrt[5])/2 = -1/a.

They are the two roots of the quadratic equation x^2 - x - 1 = 0. (Check this!)

The numbers “a” and “b” are, of course, \(\phi\) and \(1-\phi=-\phi^{-1}\). The latter is sometimes called \(-\Phi\), defining capital phi as \(\Phi=\phi^{-1}=\phi-1\approx 0.618\).

Given the formula, we can prove it by induction. This is a little different from the usual sort of induction proof, because we need to start with two base cases. We could either start with \(F_1=1, F_2=1\) as we have done above, or with \(F_0=0, F_1=1\) as he does here.

To prove Binet's Formula, first show that it is true for n = 0 and n = 1.  Then for any k >= 1, assume it is true for all n <= k (in particular for n = k and n = k-1), so that

   F(k) = (a^k-b^k)/(a-b),
   F(k-1) = (a^[k-1]-b^[k-1])/(a-b).

Now add these two equations together. The left-hand side becomes F(k+1), according to the recursion defining the Fibonacci numbers. Rearrange the right-hand side into the form

   F(k+1) = (a^k+a^[k-1]-b^k-b^[k-1])/(a-b),
          = (a^[k-1]*[a+1]-b^[k-1]*[b+1])/(a-b).

Now use the facts that a + 1 = a^2 and b + 1 = b^2, because a and b are the roots of x^2 - x - 1 = 0. Then the above expression will simplify into the form of Binet's Formula for n = k+1.

We’ll be filling in the details below.

That establishes the hypotheses of the second form of the Principle of Mathematical Induction. The conclusion of the Principle must therefore hold, and Binet's Formula is true for all integers n >= 0.

If we think of induction as a row of dominos, here we can imagine that it takes the weight of two of them to knock down the next; the conclusion is proved just as well this way.

Proving it by induction: details

An earlier question, from 1997, focused on the details:

Fibonacci Formula Inductive Proof

I am stuck on a problem about the nth number of the Fibonacci sequence. I must prove by induction that
  F(n) = (PHI^n - (1 - PHI)^n) / sqrt5

Here's what we usually do to prove something by induction:
  1) Show that the formula works with n = 1.
  2) Show that if it works for (n), then it will work for (n+1).

But the problem is:
We suppose F(n) is true, so F(n+1) is true.
But when I must prove it, I have to add another thing: F(n-1), because F(n-1) + F(n) = F(n+1).

So here are the questions: 

Can I suppose TWO things are true, F(n) and F(n-1), to prove that F(n+1) is true?

How can I prove it is true for n = 1, since F(1) is DEFINED as equal to 1?

Here's what I've already done: I've successfully converted
(PHI^(n-1) - (1 - PHI)^(n-1)) / sqrt5 + (PHI^n - (1 - PHI)^n) / sqrt5
into (PHI^(n+1) - (1 - PHI)^(n+1)) / sqrt5

Thank you very much for your much-appreciated help! An example of the Fibonacci formula inductive proof would be very kind.

Alexander

You can perhaps see that Alexander’s difficult is exactly at the point where strong induction was needed.

Doctor Rob answered the specific questions:

You have already done the hard part, which is in your next-to-last paragraph.

Answer 1.  Yes, you can assume two things are true, but then you have to show that two starting values work. (Think about it.) An equivalent formulation of the Principle of Mathematical Induction is where you assume it is true for *all* values k with 1 <= k <= n, and use that to show it for n+1.  

Answer 2.  To prove it for n = 1, you have to show that

   1 = F(1) = (PHI - 1 + PHI)/sqrt(5).

You do this by using the fact that PHI = (1 + sqrt(5))/2. Substitute it in and check that it works. To prove it for n = 2, you have to show that

   1 = F(2) = (PHI^2 - [1 - PHI]^2)/sqrt(5).

You do this the same way.  By the way, this is also true for n = 0,

   0 = F(0) = (PHI^0 - [1 - PHI]^0)/sqrt(5),

for which you don't even need the formula for PHI.

Let’s do all three of these: $$n=0\text{:  }\frac{\phi^0-(1-\phi)^0}{\sqrt{5}}=\frac{1-1}{\sqrt{5}}=0\\ n=1\text{:  }\frac{\phi^1-(1-\phi)^1}{\sqrt{5}}=\frac{\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}}{\sqrt{5}}=\frac{\sqrt{5}}{\sqrt{5}}=1\\n=2\text{:  }\frac{\phi^2-(1-\phi)^2}{\sqrt{5}}=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^2-\left(\frac{1-\sqrt{5}}{2}\right)^2}{\sqrt{5}}=\frac{\frac{6+2\sqrt{5}}{4}-\frac{6-2\sqrt{5}}{4}}{\sqrt{5}}=1$$

Alexander wrote back, not having understood strong induction:

Dear Dr. Rob,

I give up, Doctor Rob. I must use three values (F(n), F(n-1) and F(n+1)), but I can't find the way to justify this use of the induction. I know I have to show that two starting values work, but this is where I am stuck. I don't know how to show it.

Thank you very much for your time!

Doctor Rob responded by proving the “two-step” induction from the weak induction Alexander is familiar with:

I'm sorry that my previous answer was not sufficient to solve your problem. As I understand the current state of the problem, you need the following theorem to finish it:

Theorem:  If P(n) is a statement involving the variable n, and if P(1) is true, P(2) is true, and the implication P(k) & P(k+1) ==> P(k+2) is true, then P(n) is true for all n >= 1.

Proof:  We will prove this using the Principle of Mathematical Induction.

Let Q(n) be the statement "P(n) is true and P(n+1) is true." Then Q(1) holds by hypothesis. Given Q(k) is true, we know that P(k) and P(k+1) are true. Using the implication from the hypotheses of the theorem, P(k+2) is also true, so P(k+1) and P(k+2) are both true. Thus Q(k+1) is true. This means that Q(k) ==> Q(k+1). Thus by the Principle of Mathematical Induction, Q(n) is true for all n >= 1.  Q(n) ==> P(n), so P(n) is true for all n >= 1.  Q.E.D.

This is the justification you need to use your "double-step" induction. See how the need for Q(1) to be true forces us to make sure that both P(1) and P(2) are true, so we have a two-part start for the induction.

This was enough:

Thank you very much! Your answers were very complete. This is all people could expect from Dr. Math's service!

Alexander

A complete proof by induction

During this time, Doctor Anthony had answered:

                  1+sqrt(5)
Taking PHI to be  ---------,
                      2

we first check that the formula is true for n = 1 and n = 2

   F(1) = (1/sqrt(5))[(1+sqrt(5))/2 - 1 -(1+sqrt(5))/2] 

        = (1/sqrt(5))[1/2 + sqrt(5)/2 - 1/2 + sqrt(5)/2]

        = 1/sqrt(5)[sqrt(5)]

        = 1

    F(2) = (1/sqrt(5))[PHI^2 - (1-PHI)^2]

         = (1/sqrt(5)[PHI^2 - 1 + 2 PHI - PHI^2]

         = (1/sqrt(5))[2 PHI - 1]

         = (1/sqrt(5)[1+sqrt(5) - 1]

         = 1

So the formula is correct for n=1 and n=2.

As we’ve seen, we could have use n = 0 and n = 1, if Alexander were allowing n to start at 0.

Now he uses strong induction directly (without pointing out the difference):

Now assume it is true for all terms UP TO some other value n.

If we take

              1     sqrt(5)+1           1-sqrt(5)
  F(n+1) = -------[(---------)^(n+1) - (---------)^(n+1)]
           sqrt(5)       2                  2


                       (sqrt(5)+1)^2
By taking out a factor ------------- from the first term and 
                            2^2
  (1-sqrt(5))^2
  -------------  
       2^2

from the second term and then squaring out these brackets it is easy to show that  F(n+1) = F(n) + F(n-1).

So if the expression is true for n and n-1, it is also true for n+1.  But it is true for n=1 and n=2, hence it must be true for n=3. So true for n=2 and n=3 it is true for n=4. Thence to n=5, n=6, n=7 and so on to all positive integer values of n.

Let’s fill in the details. I’m going to do the reverse of his suggestion, and start from \(F(n) + F(n-1)\):

$$F_n=\frac{\phi^n-(1-\phi)^n}{\sqrt{5}}=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}\\F_{n-1}=\frac{\phi^{n-1}-(1-\phi)^{n-1}}{\sqrt{5}}=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}}{\sqrt{5}}\\F_n+F_{n-1}=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}+\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}}{\sqrt{5}}=\\ \frac{\left(\frac{1+\sqrt{5}}{2}\right)\left(\frac{1+\sqrt{5}}{2}\right)^{n-1}-\left(\frac{1-\sqrt{5}}{2}\right)\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}}{\sqrt{5}}+\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}}{\sqrt{5}}=\\ \frac{\left(\frac{1+\sqrt{5}}{2}+1\right)\left(\frac{1+\sqrt{5}}{2}\right)^{n-1}-\left(\frac{1-\sqrt{5}}{2}+1\right)\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}}{\sqrt{5}}=\\ \frac{\left(\frac{3+\sqrt{5}}{2}\right)\left(\frac{1+\sqrt{5}}{2}\right)^{n-1}-\left(\frac{3-\sqrt{5}}{2}\right)\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}}{\sqrt{5}}$$

But, going back to Doctor Anthony’s suggestion (factoring out squares to leave \(n-1\) powers), our goal is $$F_{n+1}=\frac{\phi^{n+1}-(1-\phi)^{n+1}}{\sqrt{5}}=\\ \frac{\phi^2\phi^{n-1}-(1-\phi)^2(1-\phi)^{n-1}}{\sqrt{5}}=\\ \frac{\left(\frac{1+\sqrt{5}}{2}\right)^2\phi^{n-1}-\left(\frac{1-\sqrt{5}}{2}\right)^2(1-\phi)^{n-1}}{\sqrt{5}}=\\ \frac{\left(\frac{3+\sqrt{5}}{2}\right)\phi^{n-1}-\left(\frac{3-\sqrt{5}}{2}\right)^2(1-\phi)^{n-1}}{\sqrt{5}}$$

But that is just what we have; so we have shown that \(F_{n+1}=F_n+F_{n-1}\).