Thread: Derive a formula

Originally Posted by mauro21pl

Hi
Could anyone help me with that problem:

A bit string is a string over the alphabet {0,1}. Let n be a natural number. Derive a formula for the number of bit strings of length 2n that contain 01 as a substring. Explain your answer clearly.

The total number of strings of length n is . We must subtract from that the number of strings that do not contain 01 as a substring.

But if a string does not contain 01 then it must never have a 0 followed by a 1. So all the 1s must come at the beginning of the string, followed by all the 0s, like 111...100...0. There are n+1 such strings of length n. The formula is therefore .