A fair coin

A "double-head-free" (or DHF) sequence of $n$ tosses is one of

• a sequence of length $n$ built up from the blocks "HT" and "T",
• a sequence of length $n-1$ built up from the blocks "HT" and "T", followed by a final "H"

It is standard that the number of ways of tiling a $1 \times n$ chessboard with $1\times1$ squares and $1 \times2$ dominoes is $F_{n+1}$ , the ( $n+1$ )st Fibonacci numbers. Thus we deduce that there are $F_{n+2} = F_{n+1} + F_{n}$ DHF sequences of length $n$ . Thus the probability that a sequence of $n$ tosses is DHF is $\frac{F_{n+2}}{2^n}$ In the case that $n=10$ , this is equal to $\tfrac{9}{64}$ , making the answer $9+64=\boxed{73}$ .