Fibonacci and Catalan Numbers: An Introduction

Part One

The Fibonacci Numbers

Chapter 1

Historical Background

Born around 1170 into the Bonacci family of Pisa, Leonardo of Pisa was the son of the prosperous merchant Guglielmo, who sought to have his son follow in his footsteps. Therefore, when Guglielmo was appointed the customs collector for the Algerian city of Bugia (now Bejaia), around 1190, he brought Leonardo with him. It was here that the young man studied with a Muslim schoolmaster who introduced him to the Hindu-Arabic system of enumeration along with Hindu-Arabic methods of computation. Then, as he continued his life in the mercantile business, Leonardo found himself traveling to Constantinople, Egypt, France, Greece, Rome, and Syria, where he continued to investigate the various arithmetic systems then being used. Consequently, upon returning home to Pisa around 1200, Leonardo found himself an advocate of the elegant simplicity and practical advantage of the Hindu-Arabic number system—especially, when compared with the Roman numeral system then being used in Italy. As a result, by the time of his death in about 1240, Italian merchants started to recognize the value of the Hindu-Arabic number system and gradually began to use it for business transactions. By the end of the sixteenth century, most of Europe had adjusted to the system.

In 1202, Leonardo published his pioneering masterpiece, the Liber Abaci (The Book of Calculation or The Book of the Abacus). Therein he introduced the Hindu-Arabic number system and arithmetic algorithms to the continent of Europe. Leonardo started his work with the introduction of the Hindu-Arabic numerals: the nine Hindu figures 1,2,3,4,5,6,7,8,9, along with the figure 0, which the Arabs called zephirum (cipher). Then he addressed the issue of a place value system for the integers. As the text progresses, various types of problems are addressed, including one type on determinate and indeterminate linear systems of equations in more than two unknowns, and another on perfect numbers (that is, a positive integer whose value equals the sum of the values of all of its divisors less than itself—for example, 6 = 1 + 2 + 3 and 28 = 1 + 2 + 4 + 7 + 14). Inconspicuously tucked away between these two types of problems lies the one problem that so many students and teachers of mathematics seem to know about—the notorious Problem of the Rabbits. 5

Before continuing at this point, let us mention that although Leonardo is best known for the Liber Abaci, he also published three other prominent works. The Practica Geometriae (Practice of Geometry) was written in 1220. The Flos (Flower or Blossom) was published in 1225, as was the Liber Quadratorum (The Book of Square Numbers). The latter work established Leonardo as a renowned number theorist.

Chapter 2

The Problem of the Rabbits

In the now famous Problem of the Rabbits, Leonardo introduces us to a person who has a pair of newborn rabbits—one of each gender. We are interested in determining the number of pairs of rabbits that can be bred from (and include) this initial pair in a year if

1. each newborn pair, a female and a male, matures in one month and then starts to breed;

2. two months after their birth, and every month thereafter, a now mature pair breed at the beginning of each month. This breeding then results in the birth of one (newborn) pair, a female and a male, at the end of that month; and,

3. no rabbits die during the course of the year.

If we start to examine this situation on the first day of a calendar year, we find the results in Table 2.1 on p. 6.

Table 2.1

We need to remember that at the end of each month, a newborn pair (born at the end of the month) grows to maturity, regardless of the number of days—be it 28, 30, or 31—in the next month. This makes the new maturity entry equal to the sum of the prior maturity entry plus the prior newborn entry. Also, since each mature pair produces a newborn pair at the end of that month, the newborn entry for any given month equals the mature entry for the prior month. From the third column in Table 2.1, we see that at the end of the year, the person who started with this one pair of newborn rabbits now has a total of 233 pairs of rabbits, including the initial pair.

This sequence of numbers—namely, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .—is often called the Fibonacci sequence. The name Fibonacci is a contraction of Filius Bonaccii, the Latin form for son of Bonaccio, and the name was given to the sequence in May of 1876 by the renowned French number theorist François Edouard Anatole Lucas (pronounced Lucah) (1842–1891). In reality, Leonardo was not the first to describe the sequence, but he did publish it in the Liber Abaci, which introduced it to the West.

The Fibonacci sequence has proved to be one of the most intriguing and ubiquitous number sequences in all of mathematics. Unfortunately, when these numbers arise, far too many students, and even teachers of mathematics, are only aware of the connection between these numbers and the Problem of the Rabbits. However, as the reader will soon learn, these numbers possess a great number of fascinating properties and arise in so many different areas.

Chapter 3

The Recursive Definition

Upon examining the sequence in the middle column of Table 3.1, we see that after the first two entries, each entry is the sum of the two preceding entries. For example, 1 = 1 + 0, 2 = 1 + 1, 3 = 2 + 1, 5 = 3 + 2, 8 = 5 + 3, . . ., 55 = 34 + 21. So we are able to determine later numbers in the sequence when we know the values of earlier numbers in the sequence. This property now allows us to define what we shall henceforth consider to be the Fibonacci numbers. Consequently, the sequence of Fibonacci numbers is defined, recursively, as follows:

Table 3.1

For n ≥ 0, if we let Fn denote the nth Fibonacci number, we have

1. F0 = 0, F1 = 1            (The Initial Conditions)

2. Fn = Fn−1 + Fn−2, n ≥ 2 (The Recurrence Relation)

Therefore, the sequence F0, F1, F2, F3, . . ., which appears in the middle column of Table 3.1, now has a different starting point, namely, F0, from the sequence F1, F2, F3, . . ., which appears in the third column of Table 3.1. This sequence—F0, F1, F2, F3, . . .—is now accepted as the standard definition for the sequence of Fibonacci numbers. It is one of the earliest examples of a recursive sequence in mathematics. Many feel that Fibonacci was undoubtedly aware of the recursive nature of these numbers. However, it was not until 1634, when mathematical notation had 9 sufficiently progressed, that the Dutch mathematician Albert Girard (1595–1632) wrote the formula in his posthumously published work L'Arithmetique de Simon Stevin de Bruges.

Using the recursive definition above, we find the first 25 Fibonacci numbers in Table 3.1.

Chapter 4

Properties of the Fibonacci Numbers

As we examine the entries in Table 3.1, we find that the greatest common divisor of F5 = 5 and F6 = 8 is 1. This is due to the fact that the only positive integers that divide F5 = 5 are 1 and 5, and the only positive integers that divide F6 = 8 are 1, 2, 4, and 8. We shall denote this by writing gcd (F5, F6) = 1. Likewise, gcd (F9, F10) = 1, since 1, 2, 17, and 34 are the only positive integers that divide F9 = 34, while the only positive integers that divide F10 = 55 are 1, 5, 11, and 55. Hopefully we see a pattern developing here, and this leads us to our first general property for the Fibonacci numbers.

Property 4.1: For n ≥ 0, gcd (Fn, Fn+1) = 1.

Proof: We note that gcd (F0, F1) = gcd (0, 1) = 1. Consequently, if the result is false, then there is a first case, say n = r > 0, where gcd (Fr, Fr+1) > 1. However, gcd (Fr−1, Fr) = 1. So there is a positive integer d such that d >1 and d divides Fr and Fr+1. But we know that

So if d divides Fr and Fr+1, it follows that d divides 9 Fr−1. This then contradicts gcd (Fr−1, Fr) = 1. Consequently, gcd (Fn, Fn+1) = 1 for n ≥ 0.

Using a similar argument and Property 4.1, the reader can establish our next result.

Property 4.2: For n ≥ 0, gcd (Fn, Fn+2) = 1.

To provide some motivation for the next property, we observe that

These results suggest the following:

Property 4.3: The sum of any six consecutive Fibonacci numbers is divisible by 4. Even further, for n ≥ 0 (with n fixed),

Proof: For n ≥ 0,

In a similar manner, one can likewise verify the following:

Property 4.4: The sum of any ten consecutive Fibonacci numbers is divisible by 11. In fact, for n ≥ 0 (with n fixed),

Our next property was discovered by Edouard Lucas in 1876. A few observations help suggest the general result:

Property 4.5: For , .

Proof: Although this summation formula can be established using the Principle of Mathematical Induction, here we choose to use the recursive definition of the Fibonacci numbers and consider the following:

When we add these n + 1 equations, the left-hand side gives us , while the right-hand side provides (F2 − F1) + (F3 − F2) + + (Fn+1 − Fn) + (Fn+2 − Fn+1) = − F1 + (F2 − F2) + (F3 − F3) + + (Fn − Fn) + (Fn+1 − Fn+1) + Fn+2 = Fn+2 − F1 = Fn+2 − 1.

Passing from first powers to squares, we find that

From what is suggested in these five results, we conjecture the following:

Property 4.6: For .

Proof: Here we shall use the Principle of Mathematical Induction. For n = 0, we have

. This demonstrates that the conjecture is true for this first case and provides the basis step for our inductive proof. So now we assume the conjecture true for some fixed (but arbitrary) n = k (≥ 0). This gives us Turning to the case where n = k + 1 (≥ 1), we have

Consequently, the truth of the case for n = k + 1 follows from the case for n = k. So our conjecture is true for all n ≥ 0, by the Principle of Mathematical Induction.

At this point, let us mention three more properties exhibited by the Fibonacci numbers. There are so many! The reader should find a wealth of such results in References [38, 50]. The first two of these properties are also due to Edouard Lucas from 1876. The third was discovered in 1680 by the Italian-born French astronomer and mathematician Giovanni Domenico (Jean Dominique) Cassini (1625–1712). This result was also discovered independently in 1753 by the Scottish mathematician and landscape artist Robert Simson (1687–1768). We shall leave the proofs of all three results for the reader. However, we shall obtain the result due to Cassini in another way, when we introduce a 2 × 2 matrix whose components are Fibonacci numbers in Chapter 14.

Property 4.7: For

.

Property 4.8: For

.

Property 4.9: For .

At this point, we realize that the Fibonacci numbers do possess some interesting properties. But surely there must be places where these numbers arise—other than the Problem of the Rabbits. In Chapter 5, we shall encounter some examples where these numbers arise, and start to learn why these numbers are often referred to as ubiquitous.

Exercises for Chapter 4

1. Prove Property 4.2—that is, for n ≥ 0, gcd (Fn, Fn+2) = 1.

2. Provide an example to show that gcd (Fn, Fn+3) ≠ 1 for some n ≥ 0.

3. For n ≥ 1, prove that F2(n+1) = 2F2n + F2n−1.

4. For n ≥ 2, prove that Fn+2 + Fn−2 = 3Fn.

5. For n ≥ 2, prove that Fn+2 + Fn + Fn−2 = 4Fn.

6. For n ≥ 1, prove that .

7. For n ≥ 2, prove that F3n = 4F3n−3 + F3n−6.

8. Prove that

9. Use the Principle of Mathematical Induction to prove that for n ≥ 0, .

10. Fix n ≥ 0. Prove that

11. Prove Property 4.7—that is, for .

12. Prove Property 4.8—that is, for

13. Verify the result due to Giovanni Cassini in Property 4.9 for n = 3, 4, 5, and 6.

14. Use the Principle of Mathematical Induction to prove Property 4.9—that is, for

15. For n ≥ 1, prove that .

16. Jodi starts to write the Fibonacci numbers on the board in her office, using the recursive definition. She writes the correct values for the numbers F0, F1, F2, . . ., Fn−1, but then Professor Brooks distracts her and she writes Fn + 1 instead of the actual value Fn. (a) If she does not make any further mistakes in using the recursive definition for the Fibonacci numbers, what value does she write next? (b) What does she write instead of the actual value of Fn+2? (c) In general, for r > 0, what value does she write instead of the actual value of Fn+r?

17. Use the Principle of Mathematical Induction to prove that for n ≥ 1,

(This formula is an example of a weighted sum involving the Fibonacci numbers.)

18. For n ≥ 0, prove that . (H. W. Gould, 1963) [24].

19. For n ≥ 1, prove that .

20. For n ≥ 1, prove that .

21. For n ≥ 0, prove that . (M. N. S. Swamy, 1966) [52].

22. For n ≥ 1, prove that . (K. S. Rao, 1953) [45].

23. For n ≥ 1, prove that

24.

a. For any real numbers a and b, prove that

[This result is known as Candido's identity, in honor of the Italian mathematician Giacomo Candido (1871–1941).]

b. For n ≥ 0, prove that

25. For n ≥ 0, prove that Fn+5 − 3Fn is divisible by 5. [Alternatively, this can be stated as Fn+5 ≡ 3Fn(mod5).]

26. For n ≥ m ≥ 1, prove that .

27.

a. Verify that (F3 + F4 + F5 + F6) + F4 = F8.

b. For what value of n is it true that (F4 + F5 + F6 + F7 + F8) + F5 = Fn?

c. Fix n ≥ 1 and m ≥ 1. What is (Fn + Fn+1 + Fn+2 + + Fn+m) + Fn+1quest (This fascinating tidbit was originally recognized by W. H. Huff.)

28. For n ≥ 3, prove that

Chapter 5

Some Introductory Examples

As the title indicates, this chapter will provide some examples where the Fibonacci numbers arise. In particular, one such example will show us how to write a Fibonacci number as a sum of binomial coefficients. In addition, even more examples will arise from some of the exercises for the chapter.

Example 5.1: Irving Kaplansky (1917-2006): For n ≥ 1, let Sn = {1, 2, 3, . . ., n}, and let S0 = ∅, the null, or empty, set. Then the number of subsets of Sn is 2n. But now let us count the number of subsets of Sn with no consecutive integers. So, for n ≥ 0, we shall let an count the number of subsets of Sn that contain no consecutive integers. We consider the situation for n = 3, 4, and 5. In each case, we find the empty set ∅; otherwise, there would have to exist two integers in ∅ of the form x and x + 1. Either such integer contradicts the definition of the null set. So the subsets with no consecutive integers for these three cases are as follows:

Note that when we consider the case for n = 5, only two situations can occur, and they cannot occur simultaneously:

i. 5 is not in the subset: Here we can use any of the eight subsets for S4—as we see from the first line of subsets for S5.

ii. 5 is in the subset: Then we cannot have 4 in the subset. So we place the integer 5 in each of the five subsets for S3 and arrive at the five subsets in the second line of subsets for S5. Consequently, we have a5 = a4 + a3.

The above argument generalizes to give us

The recurrence relation in this case is the same as the one for the Fibonacci numbers, but the initial conditions are different. Here we have a0 = 1 = F2 and a1 = 2 = F3. Therefore,

Example 5.2: As in Example 5.1, we shall let Sn = {1, 2, 3, . . ., n}, for n ≥ 1. Then for any nonempty subset A of Sn, we define A + 1 = {a + 1 a A}. So if n = 4 and A = {1, 2, 4}, then A + 1 = {2, 3, 5}, and we see that A ∪ (A + 1) = S5. Consequently, for n ≥ 1, we shall now let gn count the number of subsets A of Sn such that A ∪ (A + 1) = Sn+1. Such subsets A of Sn are called generating sets for Sn+1. We realize that for any such subset A, it follows that 1 A and, for n ≥ 2, n A. For n = 3, 4, and5, we find the following examples of generating sets:

Here we see that the g5 generating sets for S6 (where n = 5) are obtained from those of S5 (where n = 4) and from those of S4 (where n = 3), by placing 5 in each of the g4 generating subsets for S5 and in each of the g3 generating subsets for S4. Consequently, g5 = g4 + g3 and this particular case generalizes to

(Note that we could define g0 = 0, by extending the given recurrence relation to n ≥ 2 and solving the equation g0 = g2 − g1 to obtain g0 = 1 − 1 = 0.) Here we find that

(More on generating sets can be found in Reference [26]. A generalization of this idea is found in Reference [54].)

Example 5.3: Next we examine binary strings made up of 0's and 1's. For n ≥ 1, there are 2n binary strings of length n—that is, the strings are made up of n symbols, each a 0 or a 1. We wish to count those strings of length n, where there are no consecutive 1's. So we shall let bn count the number of such strings of length n and learn, for example, that (i) b3 = 5, for the strings 000, 100, 010, 001, 101; and (ii) b4 = 8, for the strings 0000, 1000, 0100, 0010, 0001, 1010, 1001, 0101. In general, when n ≥ 2, there are two cases to consider for a string s of length n with no consecutive 1's:

i. s ends in 0: Here the possibilities for the preceding n − 1 symbols of s constitute all of the bn−1 strings of length n − 1 with no consecutive 1's.

ii. s ends in 1 (actually 01): Now the possibilities for the preceding n − 2 symbols of s are counted by the bn−2 strings of length n − 2 with no consecutive 1's.

Consequently,

and

Is it just a coincidence that the answers for an (in Example 5.1) and for bn (here in Example 5.3) are the same? We can relate these results as follows. When n = 5, for instance, we can correspond the subset {1, 4} of Example 5.1 with the string 10010 and the subset {1, 3, 5} with the string 10101. In general, we line up the integers in Sn as 1, 2, 3, . . ., n − 1, n. Then for a string of n 0's and 1's (with no consecutive 1's), we examine the locations for the 1's. If a 1 is in the ith position, for 1 ≤ i ≤ n, we then select i from Sn to determine our corresponding subset with no consecutive integers.

Example 5.4: As in Examples 5.1 and 5.2, we again define Sn = {1, 2, 3, . . ., n − 1, n}, for n ≥ 1. Now we are interested in the functions f: Sn → Sn that are one-to-one (and consequently, onto) or onto (and consequently, one-to-one). These functions are called the permutations of Sn and they number n !. For a given n ≥ 1, we want to determine the number of these permutations f such that ≤ 1, for all 1 ≤ i ≤ n—that is, we want to count the permutations f where (i) f(1) = 1 or f(1) = 2; (ii) f(n) = n or f(n) = n− 1; and, (iii) f(i) = i − 1 or f(i) = i or f(i) = i + 1 for all 2 ≤ i ≤ n − 1. When n = 3, for instance, out of the six possible permutations for S3, we find the following three that satisfy the given condition:

For n ≥ 1, let pn count the permutations of Sn that satisfy the stated condition. There are two cases to consider:

i. f(n) = n: Here we can use any of the pn−1 permutations f: Sn−1 → Sn−1.

ii. f(n) = n − 1: When this happens it follows that f(n − 1) = n, and under these conditions we can then use any of the pn−2 permutations f: Sn−2 → Sn−2.

Consequently, we see that

and

Example 5.5: Olry Terquem (1782-1862): Again, we let Sn = {1, 2, 3, . . ., n − 1, n}, where n ≥ 1, but this time we are interested in the subsets of Sn of the form {a1, a2, a3, . . ., ak}, where (i) a1 < a2 < a3 < < ak (so k ≤ n); (ii) ai is odd for i odd, with i ≤ n; and, (iii) ai is even for i even, with i ≤ n. These sets are called the alternating subsets of Sn. When n = 3, we find five such subsets—namely, ∅, {1}, {1, 2}, {1, 2, 3}, and {3}. For n = 4, there are eight such subsets: ∅, {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}, {1, 4}, {3}, and {3, 4}. In general, for n ≥ 1, let tn count the number of alternating subsets of Sn. Then t1 = 2, t2 = 3, and, for n ≥ 3, we consider the following:

Suppose that B = {b1, b2, . . ., bk} is an alternating subset of Sn where (i) b1 < b2 < < bk; (ii) bi is odd for i odd, with i ≤ n; and, (iii) bi is even for i even, with i ≤ n. There are two cases to examine.

1. If b1 = 1, then {b2 − 1, b3 − 1, . . ., bk − 1} is an alternating subset of Sn−1. This implies that there are tn−1 alternating subsets of Sn that contain 1.

2. If b1 ≠ 1, then b1 ≥ 3 and {b1 − 2, b2 − 2, . . ., bk − 2} is an alternating subset of Sn−2. So there are tn−2 alternating subsets of Sn that do not contain 1.

Since these two cases cover all the possibilities and have nothing in common, it follows that

and

Example 5.6(a): This example is due to George Andrews. Let us start with S4 = {1, 2, 3, 4}. The set A = {2, 4} is a subset of S4 and is such that 2 (the element 2 from A) ≥, the size of A. Likewise 4≥. We call such a subset A a fat subset of S4. The subset B = {3, 4} is also a fat subset of S4, since and. However, the subset C = {1, 2} is not a fat subset of S4 because 1 C but .

In general, for n ≥ 1, a subset A of Sn is called a fatsubset of Sn if x≥ for every x A. How many fat subsets does the set Sn have?

If we let fn count the number of fat subsets of Sn, then we find that f1 = 2 for the fat subsets ∅ and {1} of S1 = {1}, and f2 = 3 for the fat subsets ∅, {1}, and {2} of S2 = {1, 2}. Now for n ≥ 3, there are two things to consider. If A is a fat subset of Sn and n ∉ A, then A is a fat subset of Sn−1. If, however, n A, then 1 ∉ A because with 1, n A, it follows that and. Upon removing n and subtracting 1 from each of the remaining integers in A, we obtain a fat subset of Sn−2. (Alternatively, we could take any fat subset for Sn−2, add 1 to each integer in the set, and then place n into the new resulting set.) Consequently,

and, as in our previous example,

But now we learn a little bit more. Note that for S4 there are eight fat subsets. This follows because from S4 = {1, 2, 3, 4}, there is one way to select the null subset, 41 ways to select a fat subset of size 1, and 32 ways to select a fat subset of size 2 (from {2, 3, 4}). Consequently, F6 = 1 + 41 + 32 = 50 + 41 + 32, a sum of binomial coefficients. In like manner, we have F7 =the number of fat subsets of S5 = 60 +51 + 42 + 33, and for n ≥ 1, it follows that

Before leaving this example, let us consider the two versions of Pascal's triangle in Fig. 5.1 on p. 18. In Fig. 5.1(a), we add the numbers along the seven diagonal lines indicated:

Figure 5.1

The resulting sums are

Now does this pattern continue or are we being misled? Well, consider the version of Pascal's triangle in Fig. 5.1(b). If we compute the same sums along the seven diagonal lines indicated in the figure, we find that

This time the results we found earlier for Fn, when we were counting fat subsets, indicate that this pattern does continue.

This pattern can also be established by the Alternative, or Strong, form of the Principle of Mathematical Induction, and the combinatorial identity

Note, for instance, how

and how

Example 5.6(b): Along the same line, let us consider the following three subsets of S10 = {1, 2, 3, . . ., 10}—namely, {2, 6}, {3, 8, 10}, and {4, 6, 8, 9}. You might wonder what, if anything, these three subsets have in common. Considering the size of each subset, we see that

|{2, 6}| = the size of {2, 6} = 2, the minimal element in {2, 6}

|{3, 8, 10}| = 3, the minimal element in {3, 8, 10}

|{4, 6, 8, 9}| =4, the minimal element in {4, 6, 8, 9}.

So now what we want to determine, for each n ≥ 1, is the number mn of subsets A of Sn where the minimal element of A equals, the size of A. To motivate the solution, we shall consider the cases for n = 4, 5, and 6.

The first five subsets for n = 6 are precisely those for the case where n = 5. But what about the last three subsets for n = 6? Since 6 is a member of each such subset, the minimal element is at least 2. Turning to the three subsets for n = 4, in each case we increase each element in the subset by 1 and then add in the element 6. (Since the largest possible element in any subset of S4 is 4, there is no danger that 6 will come about as k + 1 for some k in a subset of S4.) Consequently,

So

The same type of argument can be given for each n ≥ 3, so we arrive at the recurrence relation

and, consequently, mn = Fn, for n ≥ 1.

We can also obtain the result for n = 7, for example, by the following alternative argument:

1. There is one subset when the minimal element is 1—namely, {1}.

2. For the minimal element 2, there are 51 subsets, since we select one of the five elements 3, 4, 5, 6, and7.

3. When the minimal element is 3, there are 42 subsets—for here two elements are selected from the four elements 4, 5, 6, and7.

4. There is only one subset when the minimal element is 4—namely, {4, 5, 6, 7}.

So in total,