Browse · MATH
Printjmc
counting and probability senior
Problem
Consider sequences that consist entirely of 's and 's and that have the property that every run of consecutive 's has even length, and every run of consecutive 's has odd length. Examples of such sequences are , , and , while is not such a sequence. How many such sequences have length 14?
Solution
Let and denote, respectively, the number of sequences of length ending in and . If a sequence ends in an , then it must have been formed by appending two s to the end of a string of length . If a sequence ends in a it must have either been formed by appending one to a string of length ending in an , or by appending two s to a string of length ending in a . Thus, we have the recursionsBy counting, we find that .Therefore, the number of such strings of length is .
Final answer
172