Code Kata Fifteen -- A Diversion

Some sequences just keep turning up.

A Diversion

At my son's karate school, they spend most of their time doing various exercises, with the occasional round of sparring thrown in. But every now and then the teacher finds a way to break the routine by injecting some kind of game or surprise into the mix. This kata is one of those. It's nothing serious, and unlikely to have practical benefits (unless you're working in some fairly specialized areas).

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?

---

I'm trying to track down a definitive source for this relationship: if anyone has a reference I'd love to see it. Thanks...

Comments

[Jeff]

2^(n-1) + 1

[Dave Thomas]

'fraid not...

[Peter Christensen]

It's a Fibonacci sequence. 1 bit = 2, 2 bits = 3, 3 bits = 5, etc.
If you look at have already calculated the nth # of bits, then n+2 is four groups of the same numbers, each preceded by 00, 01, 10, 11.
The first one is the same as n, the second one will eliminate all numbers that have a 1 in the high order bit. These first two groups, when combined, is the solution to n+1.
The third group gives the same result as n, and in the fourth group, no numbers qualify (11 doesn't qualify by definition). So the third+fourth group = n.
So:

f(n+2) = 1st+2nd+3rd+4th blocks
f(n+2) = (1st+2nd) + (3rd+4th)
f(n+2) = f(n+1) + f(n)
f(n+2) = f(n) + f(n+1)

Which is the definition of the Fibonacci sequence. Sorry about the sloppy mathematical notation.

-Peter

[Spikey]

Peter's correct. The answer is f(n+2) where f(n) is the Fibonacci sequence. (i.e. f(1)=1, f(2)=1, f(3)=2, f(4)=3, f(5)=5 etc..).
For 3 bits: f(3+2) = 5.
For 4 bits: f(4+2) = 8.
etc...

Now the question is, what's the answer for this puzzle if we change it to 3 adjacent bits? 4 adjacent bits? m adjacent bits?

[g]

If you forbid m adjacent 1-bits, then the permitted n-bit numbers are those that begin with 0,1,...,m-1 adjacent 1s followed by a 0. Hence f(n) = f(n-1) + ... + f(n-m). (That holds for n>=m. For smaller n, you can either say directly that the number is 2^n or else set f(0)=1 and f(anything negative)=0 and use the recurrence for 1 onwards.)

Next question: fix m; then, when n is Very Large, roughly how big is f(n)? There's some nice mathematics behind this...

[Paul]

f(n) = (ways to start number with 0) + (ways to start number with 1)

If the number starts with 0, the problem reduces to the n - 1 case. If the number starts with 1, the next bit must be 0, and we reduce to the n - 2 case.

So, for n > 2, f(n) = f(n - 1) + f(n - 2).