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^{n}.

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.

*n* |
|*S*_{n}| |
*f(n)* |

0 | 1 | 1 |

1 | 2 | 2 |

2 | 4 | 3 |

3 | 8 | 5 |

4 | 16 | 8 |

5 | 32 | 13 |

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:

*S*_{n} = CONCAT(0,*S*_{n-1}) union CONCAT(1,*S*_{n-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,*S*_{n-1}) = CONCAT(11,*S*_{n-2}) union CONCAT(10,*S*_{n-2})

Hence *S*_{n} can be seen as the union of three disjoint sets:

*S*_{n} = CONCAT(0,*S*_{n-1}) union CONCAT(11,*S*_{n-2}) union CONCAT(10,*S*_{n-2})

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

Let *A* = CONCAT(0,*S*_{n-1})
Let *B* = CONCAT(11,*S*_{n-2})
Let *C* = CONCAT(10,*S*_{n-2})
*S*_{n} = *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:

*F*_{n} = CONCAT(0,*F*_{n-1}) union CONCAT(10,*F*_{n-2})

and

*f*(*n*) = |*F*_{n}|
= |CONCAT(0,*F*_{n-1})| + |CONCAT(10,*F*_{n-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^{n} - *fibonacci*(*n*).)