Mock AIME 1 2007-2008 Problems/Problem 8
A sequence of ten s and/or s is randomly generated. If the probability that the sequence does not contain two consecutive s can be written in the form , where are relatively prime positive integers, find .
Let denote the number of sequences of length that do not contain consecutive s. A sequence of length must either end in a or a . If the string of length ends in a , this string could have been formed by appending a to any sequence of length , of which there are such strings. If the string of length ends in a , this string could have been formed by appending a (to avoid consecutive s) to any sequence of length , of which there are such strings. Thus, we have the recursion Solving for initial conditions, we find . Thus we have the Fibonacci sequence with shifted indices; indeed , so . The probability is , and .
|Mock AIME 1 2007-2008 (Problems, Source)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|