Mock AIME 1 2007-2008 Problems/Problem 8

Problem

A sequence of ten $0$s and/or $1$s is randomly generated. If the probability that the sequence does not contain two consecutive $1$s can be written in the form $\dfrac{m}{n}$, where $m,n$ are relatively prime positive integers, find $m+n$.

Solution

Let $a_n$ denote the number of sequences of length $n$ that do not contain consecutive $1$s. A sequence of length $n$ must either end in a $0$ or a $1$. If the string of length $n$ ends in a $0$, this string could have been formed by appending a $0$ to any sequence of length $n-1$, of which there are $a_{n-1}$ such strings. If the string of length $n$ ends in a $1$, this string could have been formed by appending a $01$ (to avoid consecutive $1$s) to any sequence of length $n-2$, of which there are $a_{n-2}$ such strings. Thus, we have the recursion $$a_n = a_{n-1} + a_{n-2}$$ Solving for initial conditions, we find $a_1 = 2, a_2 = 3$. Thus we have the Fibonacci sequence with shifted indices; indeed $a_n = F_{n+2}$, so $a_{10} = F_{12} = 144$. The probability is $\frac{144}{2^{10}} = \frac{9}{64}$, and $m+n=\boxed{073}$.

See also

 Mock AIME 1 2007-2008 (Problems, Source) Preceded byProblem 7 Followed byProblem 9 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
Invalid username
Login to AoPS