# 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

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 ^{n}v = (f(n+1), f(n+2))^{T},*eigenvectors* of A, for which multiplying by high powers of A is a breeze. Two such vectors are *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^{n}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^{(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.)

### 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

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny