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
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 Anv = (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,
Now apply repeatedly (2) to (3) and bear in mind (1). We get
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
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.
