A Solution to Kata Fifteen

What fun! Dave's latest Kata is a little math problem, and it features everyone's second favorite example of recursion.

Think of binary numbers: sequences of 0's and 1's. How many n-digit binary numbers are there that don't have two adjacent 1 bits? For example, for three-digit numbers, five of the possible eight combinations meet the criteria: 000, 001, 010, 011, 100, 101, 110, 111. What is the number for sequences of length 4, 5, 10, n?

Flexing the "proofs" part of my brain for the first time in long while, I think I've got both the solution and a proof for this. I've developed this solution independently, so there are probably more elegant proofs available.

Spoiler Warning: If you'd like to work this Kata yourself, beware, spoilers follow. I'll leave some blank space first.

 ... 

spoilers follow

 ... 

Definitions and Notation

First, let's define some terms.

Let S_n be the set of binary sequences of length n. Note that |S_n| = 2ⁿ.

Let F_n be the set of sequences of binary sequences of length n that do not contain two consecutive 1 bits. The Kata asks us to determine |F_n|. I'll call that f(n).

By inspection, it's easy to work out the first few values of f(n). Note that when n=0, we can count the empty sequence.

To make the proof a little bit easier, I'll introduce some additional notation.

Let concat(a,b) be a function that maps a pair of sequences to a new sequence by prefixing the first to the second. For example, concat(1,0) = 10 and concat(10,1101) = 101101.

Let CONCAT(a,B) be function that maps a sequence and a set of sequences to a new set of sequences obtained by prefixing the sequence a to each sequence in the set B. In other words, CONCAT(s,T) := { concat(s,t) : t in T }.

The Theorem

If you're familiar with it, it is easy to recognize f(n) to be the Fibonacci Sequence, at least for small values of n. So here it is in theorem form: If f(n) is the number of binary sequences of length n that do not contain two consecutive 1 bits, then:

f(0) = 1
f(1) = 2
f(n) = f(n-1) + f(n-2) for all n > 1

The Proof

That f(0) = 1 and f(1) = 2 can be readily seen by inspection. We'll only need to demonstrate the part of the theorem that applies to n >= 2.

Note that the set S_n can be seen as the union of two disjoint sets derived from S_n-1, those that start with a 0 and those that start with a 1:

Sn = CONCAT(0,Sn-1) union CONCAT(1,Sn-1)

Similarly, CONCAT(1,S_n-1) can be seen as the union of two disjoint sets derived from S_n-2, those that start with 11 and those that start with 10:

CONCAT(1,Sn-1) = CONCAT(11,Sn-2) union CONCAT(10,Sn-2)

Hence S_n can be seen as the union of three disjoint sets:

Sn = CONCAT(0,Sn-1) union CONCAT(11,Sn-2) union CONCAT(10,Sn-2)

For convenience, let's name each of those three sets:

Let A = CONCAT(0,Sn-1)
Let B = CONCAT(11,Sn-2)
Let C = CONCAT(10,Sn-2)
Sn = A union B union C

Since the sets A, B and C represent a proper partitioning of S_n, we can determine F_n by determining the sequences that meet the conditions in each of the sets independently.

How many sequences in A are in F_n? The answer must be f(n-1), since prefixing a 0 bit won't change whether or not a sequence contains two consecutive 1 bits.

How many sequences in B are in F_n? The answer must be 0, since our prefix alone already rules out all of those sequences.

How many sequences in C are in F_n? The answer must be f(n-2), since prefixing 10 won't change whether or not a sequence contains two consecutive 1 bits.

Hence:

Fn = CONCAT(0,Fn-1) union CONCAT(10,Fn-2)

and

f(n) = |Fn|
     = |CONCAT(0,Fn-1)| + |CONCAT(10,Fn-2)|
     = f(n-1) + f(n-2)

Q.E.D.

Comments

For some reason, I had initially thought I'd be clever and reverse the problem. Why count the number of sequences that don't meet some condition, but instead count those that do? This yields the sequence 0, 0, 1, 3, 8, 19, .... Other that starting with the Fibonacci-like 0, 0, it didn't seem recognizable at all to me. (More generally, this sequence is 2ⁿ - fibonacci(n).)