When the Counting Gets Tough,
the Tough Count on Mathematics

by William A. McWorter Jr.

Consider the counting problem

How many sequences of 1's and 2's sum to 14?

To get a feeling for the problem, let's do the counting when the sum is small. Let f(n) be the number of sequences of 1's and 2's which sum to n. f(1) = 1 because there is only one way that a sequence of 1's and 2's sum to 1, namely, 1 = 1. f(2) = 2 because there are exactly two ways a sequence of 1's and 2's can sum to 2, namely, 1 + 1 = 2 and 2 = 2. f(3) = 3 because 1 + 1 + 1 = 1 + 2 = 2 + 1 = 3.

As we go on computing f(n) for small values of n, no obvious formula emerges. However, we do notice a relationship between f(n) and f(n-1) and f(n-2). For, suppose we split the sequences of 1's and 2's that sum to n into two groups, those that end in 1 and those that end in 2. For those sequences that end in 1, their sums, not counting the last 1 is a sequence of 1's and 2's that sum to n-1, and all such actually. Hence the number of sequences of 1's and 2's that sum to n and end in a 1 is f(n-1). Similarly, the number of sequences of 1's and 2's which sum to n and end in a 2 is f(n-2). Hence f(n) = f(n-1) + f(n-2), for n > 2, a so-called recursion formula for f(n).

This is of great help in solving our counting problem. Repeatedly applying this recursion formula, we get f(14) = 610, that is, there are 610 sequences of 1's and 2's which sum to 14.

This recursion formula comes up again and again. It is the recurrence formula for the famous Fibonacci sequence introduced by Leonardo Fibonacci in 1202.

How many bit strings of length n are there of 0's and 1's that contain no substring 00?

Let B(n) be the number of bit strings of length n which contain no substring 00. Split such bit strings into two groups, those that end in 1 and those that end in 0. The first group has B(n-1) bit strings with no substring 00, and the second group has B(n-2) bit strings with no substring 00 because the second last bit must be a 1. Thus B(n) = B(n-1) + B(n-2), n > 2. Grunt work shows that B(1) = 2 and B(2) = 3.

How many subsets are there (including the empty set) of the integers from 1 to n which contain no consecutive integers?

Let S(n) be the number of subsets of the integers from 1 to n which contain no consecutive integers. Split these subsets into two groups, those which don't contain n and those which contain n. The first group consists of those subsets of 1 to n-1 that contain no consecutive integers, so this group has S(n-1) members. The second group has S(n-2) members because no member of this group can contain n-1 and must contain n. S(1) = 2 and S(2) = 3.

The recurrence formula for these problems and our work on the first problem allows us to immediately conclude that B(14) = S(14) = 987 = f(15) = f(14) + f(13). The different answers here occur because B and S begin with B(1) = S(1) = 2, whereas f began with f(1) = 1.

The recurrence formula can be used to generate the Fibonacci sequence. Starting with f(0) = f(1) = 1, the recurrence formula yields a few first terms of the : 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... However, it can be very tedious to use when n is large. Enter deeper mathematics.

Those who know matrix theory can try the following. We can think of the Fibonacci sequence as generated by an iterative process. Let A be the 2 by 2 matrix

Then

(1)

Let v be the vector (1,2)^T, where "T" denotes the transpose of a vector. (Transpose of a column-vector is a row-vector and vice versa.) Then Aⁿv = (f(n+1), f(n+2))^T, for all n ≥ 0. But computing high powers of the matrix A is a real pain. Not to worry, for there are special vectors, called eigenvectors of A, for which multiplying by high powers of A is a breeze. Two such vectors are (a - 1, 1) and (-a, 1), where a = (1 + √5)/2, the golden section. Indeed,

(2)

Thus multiplying eigenvectors by A is the same as multiplying by a number, the so-called eigenvalue associated with the eigenvector.

What's this to do with Aⁿv? Well, it turns out that the above two eigenvectors are linearly independent, so v is a linear combination of them, namely,

(3)

Now apply repeatedly (2) to (3) and bear in mind (1). We get

Reading off the bottom entry of each side of the vector equation above, we have

an explicit formula for f(n); no more tedious repeated applications of the recurrence formula for f(n). The formula can be further simplified to

(4)

f(n) = (a⁽ⁿ⁺¹⁾ - (1-a)⁽ⁿ⁺¹⁾)/√5,

which is known as Binet's formula (it was first published by Euler in 1765, and later rediscovered by Jacques Binet in 1843. There is an inductive proof of Binet's formula.)

Note 1

The Fibonacci numbers pop up in a multitude of places in mathematics and nature. A very comprehensive site covering a variety of properties of Fibonacci numbers was created by Dr. Ron Knott from the University of Surrey.

Note 2

As a follow up, it so happens that two apparently unrelated geometric problems can be described by a system of linear equations (hence, by a single matrix equation): Construct a polygon by the midpoints of its edges and Find a sequence of pairwise touching circles with centers at the vertices of a given polygon.

References

A. T. Benjamin, J. F. Quinn, Proofs That Really Count, MAA, 2003
R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
H. E. Huntley, The Divine Proportion, Dover, 1970

Fibonacci Numbers

Golden Ratio in Geometry