13. (3b, 8-11) A coin is tossed 10 times. Find the probability that two heads never appear consecutively.

#
# Solution.

## First Method:

The total number of outcomes when tossing a coin ten times is $2^{10}$.

Let's find the number of combinations where no two heads appear consecutively. If there are no heads at all, then the sequence consists of ten tails, and there is only one such sequence. If there is one head, then there are $C_{10}^{1}=10$ such combinations (the head can be in any of the 10 positions). If there are two heads, then there are $C_{9}^{2}=36$ combinations (we count the number of ways to place 2 heads among 8 tails or at the ends). And so on. If there are $k$ heads, then the number of combinations is $C_{11-k}^{k}$ (the number of ways to place $k$ heads in $11-k$ positions between tails and at the ends).

Thus, the total number of combinations is $1+C_{10}^{1}+C_{9}^{2}+C_{8}^{3}+C_{7}^{4}+C_{6}^{5}=144$. Therefore, the probability is $\frac{144}{2^{10}}=\frac{9}{64}$.

## Second Method:

Let the coin be tossed $n$ times, and let $f(n)$ be the number of ways to toss the coin without two consecutive heads. The number of valid combinations where the last $n$-th position is a tail is $f(n-1)$. The number of valid combinations where the last position is a head is $f(n-2)$, because a tail must be in the second-to-last position before the head. Thus, $f(n)=f(n-1)+f(n-2)$. Additionally, $f(1)=2, f(2)=3, \ldots, f(10)=144$. The total number of outcomes for 10 coin tosses is $2^{10}$. Therefore, the desired probability is $\frac{144}{2^{10}}=\frac{9}{64}$.

Answer: $\frac{9}{64}$.