4. (7 points) A fair coin is tossed $n$ times. Find the probability that no two consecutive tosses result in heads?
Solution: Let O denote heads and P denote tails. Let $S_{n}$ be the number of sequences of O and P of length $n$ in which there are no two consecutive O symbols (we will call such sequences correct). Obviously, $S_{1}=2$ and $S_{2}=3$. We will find a recurrence formula for calculating $S_{n}$ for $n>2$.

Consider all possible sequences of length $n$ ending in P. Obviously, such a sequence will be correct if and only if the sequence without the last P symbol is correct. There are exactly $S_{n-1}$ such sequences.

Now consider all sequences of length $n$ ending in O. Obviously, such a sequence will be correct if and only if the sequence without the last two symbols P and O (the penultimate symbol must be P) is correct. Therefore, there are exactly $S_{n-2}$ such sequences.

We obtain the recurrence formula for calculating $S_{n}$:

$$
S_{1}=2, \quad S_{2}=3, \quad S_{n}=S_{n-1}+S_{n-2} \quad \text{for } n>2
$$

Obviously, this is just a shifted Fibonacci sequence $S_{n}=f_{n+2}$. The final probability is calculated using the formula $\frac{f_{n+2}}{2^{n}}$.

Answers:

| Variant | 1 | 2 | 3 | 4 | 5 | 6 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| Answer | 0.140625 | 0.140625 | 0.173828125 | 0.173828125 | 0.21484375 | 0.21484375 |


| 7 | 8 | 9 | 10 | 11 |
| :---: | :---: | :---: | :---: | :---: |
| 0.265625 | 0.265625 | 0.328125 | 0.328125 | 0.265625 |