OMCOFS: a Fibonacci pattern

When I first scanned through assignment 2, I was somewhat afraid to dig into question 1. OMCOFS (a.k.a Odd Maximal Contiguous Ones Free Strings) seems complicated just by looking at its name. It sounds very scientific and high-level,  like something that would appear in science-fiction movies, something along the lines of UFO. But it turns out that these scary-looking binary strings are much more comfortable to deal with than UFOs. 

Since we have to develop a recurrence, I start the question by first listing some examples of OMCOFS with increasing lengths and trying to find a pattern. I do this by first writing down all the possible binary strings of a particular length, then pick out those ones that are OMCOFS. This is not hard to do for binary strings of lengths 0, 1, 2, 3, and 4. But it becomes more difficult for lengths of 5 or more. I know that there are 2^5 = 32 possible binary strings of length 5, but I can only list 31. I don't know which binary string I'm missing. In the end I had to turn to the wonderful, multi-purpose Python. With the help of a little Python program, I can finally get all the possible binary strings up to length 5 and pick out the OMCOFS.

n      number of OMCOFS      OMCOFS
0                   1                        empty string
1                   1                                0
2                   2                             00, 11
3                   3                       000, 110, 011
4                   5           0000, 1100, 0110, 0011, 1111
5                   8      00000, 11000, 01100, 00110, 11110,
                            00011, 11011, 01111

 

From the "number of OMCOFS column", it is obvious that the recurrence is related to the Fibonacci sequence, but with the numbers shifted upwards. Where the Fibonacci sequence starts with 0, 1, 1, 2, 3, 5..., our recurrence starts with 1, 1, 2, 3, 5, 8... .

 

So we know that the recurrence is:

 

H(n) =    1                            if n < 2

               H(n-1) + H(n-2)    if n >= 2 

 

Now the question becomes: how do I explain why this recurrence correctly counts the number of OMCOFS of length n? It is not enough to just say I found it by looking at the pattern generated by the first few OMCOFS, and it will always be true. There has to be some pattern in the strings themselves such that the strings of length n-1 and n-2 somehow give rise to the strings of length n. But wait! This whole idea of strings sounds strikingly similar to something we did in lecture one day! As I furiously flipped through my past lecture notes, I came across the recurrence of "the number of binary strings without adjacent 0s". The idea is that, to obtain all the binary strings of length n without adjacent 0s, we append a 1 to the binary strings of length n-1 without adjacent 0s, and append a 10 to those of length n-2. With this idea in mind, I come back to our recurrence H(n). I discover that to obtain all the OMCOFS of length n, we just append a 0 to the OMCOFS of length n-1 and append a 11 to those of length n-2! The pattern is explicitly displayed by the OMCOFS I listed above, and it explains why, in numerically terms, we would have a Fibonacci pattern. The number of OMCOFS of length n is just the sum of the number of OMCOFS of length n-1 and n-2.

 

With the first obstacle cleared, I happily go on to unwind the recurrence. ^_^