The total number of strings of length n is . We must subtract from that the number of strings that donotcontain 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 .