Problem:
There are possible -letter strings in which each letter is either an or a . Find the number of such strings that do not have more than adjacent letters that are identical.
Solution:
Let , and be the number of acceptable strings of length that begin with exactly or of the same letter, respectively. For , , and . Using the fact that , and , the recursion can be used to find the first terms of the sequence to be , and . The number of strings of length that satisfy the requirement is .
The problems on this page are the property of the MAA's American Mathematics Competitions