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.
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
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
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
The recurrence formula for these problems and our work on the first problem allows us to immediately conclude that
The recurrence formula can be used to generate the Fibonacci sequence. Starting with
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
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
What's this to do with Anv? Well, it turns out that the above two eigenvectors are linearly independent, so v is a linear combination of them, namely,
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
f(n) = (a(n+1) - (1-a)(n+1))/√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.)
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.
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.
- 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
Copyright © 1996-2018 Alexander Bogomolny