Just felt like doing some programming exercise. My bookmarks led me to the code kata 15. First, the problem:

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?Having worked out the pattern, there’s a second part to the question: can you prove why that relationship exists?

Now, the solution.

Let’s call the function that calculate the number of n-digit binary numbers without two adjacent **1** bits **a(n)**.

Now let’s define two helper functions. **a _{0}(n)** returns number of those binary numbers that end with zero, and

**a**returns number of those ending with one. Thus, it’s obvious that:

_{1}(n)a(n) = a

_{0}(n) + a_{1}(n)

Now, suppose we already have a set of (n-1)-bit numbers generated and now, based on that, we want to generate a new set of n-bit numbers. We’ll do that by adding a single bit to the end of each (n-1)-bit number. Because we care only about adjacent **1s**, we can add **0s** to the end of every (n-1)-bit number. Thus:

a

_{0}(n) = a(n-1)

On the other hand we can’t add **1s** to each (n-1)-bit number. We can only add **1** to numbers which had **0** at the end. Thus:

a

_{1}(n) = a_{0}(n-1)

By simple substitution we can rewrite the last equation into the following one:

a

_{1}(n) = a(n-2)

Get back to the definition of **a _{0}(n)** and

**a**and make the final substitution:

_{1}(n)a(n) = a(n-1) + a(n-2)

Doesn’t it look familiar? Now you only have to say that **a(1) = 2** and **a(2) = 3** and you’re done.