A coin is flipped multiple times until an odd number of heads followed by a tail is obtained. Given $n \in \mathbb{N}^{*}$, find the number of sequences of $n$ flips.
Without generating function: Let $a_{n}$ be the number of sequences of $n$ coin tosses. It is easily verified that $a_{0}=0, a_{1}=0, a_{2}=1$. Then, for $n \geqslant 3$, any sequence of tosses starts either with $P$, or with $F F$, and the sequence obtained by removing this remains valid. Conversely, we can add $P$ or $F F$ to any valid sequence to obtain a new valid sequence. Therefore, $a_{n+2}=a_{n+1}+a_{n}$, which is the Fibonacci recurrence, meaning that $a_{n+1}=F_{n}$. With generating function: A valid sequence of tosses looks like this:

![](https://cdn.mathpix.com/cropped/2024_05_10_10c029b6c4865f8b8ca3g-377.jpg?height=177&width=780&top_left_y=2453&top_left_x=638)

So the corresponding generating function is

$$
\begin{aligned}
& \underbrace{\frac{1}{1-X}}_{\text {heads }}(\underbrace{(1+\underbrace{\frac{X^{2}}{1-X^{2}}}_{\text {even tails } \geqslant 2} \underbrace{\frac{X}{1-X}}_{\text {heads }}+\left(\frac{X^{2}}{1-X^{2}} \frac{X}{1-X}\right)^{2}+\ldots) \underbrace{\frac{X}{1-X^{2}}}_{\text {odd tails }} \underbrace{X}_{\text {final head }}}_{\text {alternation of tails/heads }} \\
& =\frac{X^{2}}{(1-X)^{2}(1+X)} \frac{1}{1-\frac{X^{3}}{(1-X)^{2}(1+X)}} \\
& =\frac{X^{2}}{(1-X)^{2}(1+X)-X^{3}} \\
& =\frac{X^{2}}{1-X-X^{2}}
\end{aligned}
$$

So the answer is $F_{n-1}$.