probability of beeps A machine can beep in either of two ways. It can either BEEP or it can BOOP. It sends out a test message in the form of ten beeps, with each beep being either BEEP or BOOP, with either one of them happening with equal likeliness. What is the probability that two BOOPs are not heard consecutively?
I don't know where to start. There are $2^{10}$ ways the message can be sent out. However, there are so many cases to consider that I don't know if casework can be applied, or can even help. How can I do this?
 A: If no two BOOPs are heard together that means that every BOOP is followed by a BEEP, unless a BOOP is the last sound.  The exceptional case makes things hard to count, so get rid of it:  Pretend that there are eleven sounds, the last of which is always a BEEP.
Now one can easily count the number of possibilities with a given number of BOOPs (each with a following BEEP attached, treated as a single BOOP-BEEP unit):


*

*No BOOPs: There are $11$ BEEPs, $1$ possibility.

*1 BOOP-BEEP: There must also be $9$ BEEPs; one just needs to choose which of the ten items is the BOOP-BEEP; $\binom{10}{1} = 10$ possibilities.

*2 BOOP-BEEPs: Plus $7$ BEEPs; $\binom{9}{2} = 36$ possibilities.

*3 BOOP-BEEPs: Plus $5$ BEEPs; $\binom{8}{3} = 56$ possibilities.

*4 BOOP-BEEPs: Plus $3$ BEEPs; $\binom{7}{4} = 35$ possibilities.

*5 BOOP-BEEPs: Plus $1$ BEEP; $\binom{6}{5} = 6$ possibilities.


There cannot be $6$ or more BOOPs, since there need to be at least five BEEPs to separate them.  So the total is $1 + 10 + 36 + 56 + 35 + 6 = 144$ possibilities without consecutive BOOPs out of $2^{10} = 1024$ total possibilities.  The probability of having no consecutive BOOPs is thus $144/1024 = 9/64$.

EDIT: Another method.
Let $a_n$ be the number of sequences of $n$ BEEPs and BOOPs without two consecutive BOOPs.  Clearly $a_1 = 2$ and $a_2 = 3$.
For $n > 2$, we can compute $a_n$ by considering two alternatives:


*

*The first sound is a BEEP.  Thereafter we can have any sequence of $n-1$ sounds without two consecutive BOOPs; there are thus $a_{n-1}$ possibilities.

*The first sound is a BOOP.  It must be followed by a BEEP; after that we can have any sequence of $n-2$ sounds without two consecutive BOOPs: $a_{n-2}$ possibilities.
This yields the familiar recurrence $a_n = a_{n-1} + a_{n-2}$.  Since $a_1 = 2$ is the third Fibonacci number, $F_3$, and $a_2 = 3$ is the fourth, $F_4$, it must be that $a_n = F_{n+2}$.  Hence the total number of sequences of $10$ sounds without two consecutive BOOPs is $F_{12} = 144$.
