# A Solution to Kata Fifteen

**Friday, 22 August 2003**

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}*

*n*. Note that

*S*| = 2

_{n}^{n}

Let *F _{n}*

*n*that do not contain two consecutive 1 bits. The Kata asks us to determine

*F*|

_{n}*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,

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,
*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) = 1f(1) = 2f(n) =f(n-1) +f(n-2) for alln> 1

## The Proof

That *f*(0) = 1*f*(1) = 2*n* >= 2

Note that the set *S _{n}*

*S*

_{n-1}S= CONCAT(0,_{n}S) union CONCAT(1,_{n-1}S)_{n-1}

Similarly, *S _{n-1}*)

*S*

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

Hence *S _{n}*

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

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

LetA= CONCAT(0,S) Let_{n-1}B= CONCAT(11,S) Let_{n-2}C= CONCAT(10,S)_{n-2}S=_{n}AunionBunionC

Since the sets *A*, *B* and *C* represent a proper partitioning of *S _{n}*

*F*

_{n}
How many sequences in *A* are in
*F _{n}*

*f*(

*n-1*)

How many sequences in *B* are in
*F _{n}*

How many sequences in *C* are in
*F _{n}*

*f*(

*n-2*)

Hence:

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

and

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