refer to the sequence S where S subset of n denotes the number of n-bit strings that do not contain the pattern 00. Show that S_n = f_(n+2,) n = 1, 2, …, where ƒ denotes the Fibonacci sequence.

Question

anonymous · Answer

Let's say we have a 2-bit string. If it starts with $1$ (i.e. the string is $1x$ where $x$ is a $1$ or $0$), how may possible strings are there that don't contain $00$? What if the string starts with $0$ ($0x$)?

anonymous · Answer

Now suppose we have a 3-bit string. How many strings $1xx$ don't contain $00$? How many strings $0xx$?

The 3-bit strings starting with $1$ is the same as the total number of 2-bit strings, while the 3-bit strings starting with $0$ MUST be the same as the number of 2-bit strings that started with $1$ (otherwise we'd get a string with $00$).

See where this is going?