### Due November 22

This problem is best solved by working out examples. We consider this to be an medium problem, worth 15 points, though a closed form solution is hard (and worth 25 points). Send answers and questions to mathstat@uoguelph.ca

Suppose we are looking a strings of letters with only the letters "A" and "B". The first few would be A, B, AA, AB, BA, BB, AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB, and so on. Since each string can be made longer by adding an A or a B the number of strings with some number n of characters is twice as many as the number of strings with n-1 characters. The number of strings of length 1 is 2, the number of strings of length 2 is 4, the number of strings of length 3 is 8, and so on.

Suppose that we want to count the number of strings that never have two B's next to one another? How many strings are there of each length? The first few strings like this are: A, B, AA, AB, BA, AAA, AAB, ABA, BAA, BAB, AAAA, and so on. Advanced students may want to try to find a formula for the number of strings with n characters to get 25 points; anyone may explain how the numbers are generated to get 15 points.