Binary strings with no two 1s in a row

Question

Consider strings of length 10 made of the symbols 0 and 1, such as 0100101001.

How many such strings contain no two 1s next to each other? Find the pattern for shorter lengths first, and explain the recursion.

Accepted Answer

144 strings. The recursion. Let S(n) be the number of valid strings of length n. A valid string of length n ends in 0 or in 1. - If it ends in 0, the first n minus 1 symbols form any valid string of length n minus 1: S(n minus 1) possibilities. - If it ends in 1, the symbol before it must be 0 (no two 1s together), and the first n minus 2 symbols form any valid string of length n minus 2: S(n minus 2) possibilities. So S(n) = S(n minus 1) + S(n minus 2), with S(1) = 2 (the strings 0 and 1) and S(2) = 3 (00, 01, 10). The sequence runs 2, 3, 5, 8, 13, 21, 34, 55, 89, 144: the Fibonacci numbers,…

Binary strings with no two 1s in a row

Your answer

Discussion

Learn the concepts

Related questions