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 ?
Solution:
Let and be the number of permissible sequences of length beginning with and , respectively, and let be the total number of permissible sequences of length . Any permissible sequence of length that begins with must begin with followed by a permissible sequence of length , so that for . Any permissible sequence of length that begins with must begin with a single followed by a permissible sequence of length beginning with , or else it must begin with followed by a permissible sequence of length beginning with . Thus for , and hence . Because , it follows that
and so for . Note that the permissible sequences of length at most are , and . Thus , and . Applying these results to the recursion given above produces the sequence , , and , and the required value is .
The problems on this page are the property of the MAA's American Mathematics Competitions