How many sequences of ten binary digits are there in which neither two zeroes nor three ones ever appear in a row?
Solution
Let be the number of binary sequences of length satisfying the conditions and ending in 0 , let be the number ending in 01 , and let be the number ending in 11 . From the legal sequences of length , we find that . We now establish a recursion by building sequences of length from sequences of length . We can add a 0 to a sequence of length if and only if it ended with a 1 , so . We can have a sequence of length ending with 01 only by adding a 1 to a sequence of length ending in 0 , so . We can have a sequence of length ending with 11 only by adding a 1 to a sequence of length ending in 01 , so . We can now run the recursion: Our answer is then .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.