Toss a fair coin n times. What is the probability that the sequence contains no HH?
Key idea
Count valid sequences, then divide by all 2n equally likely sequences.
T
Ends in T: the first n−1 tosses can be any valid sequence, giving aₙ₋₁ possibilities.
TH
Ends in H: the previous toss must be T. Append TH to any valid sequence of length n−2, giving aₙ₋₂ possibilities.
aₙ = aₙ₋₁ + aₙ₋₂
a₀ = 1, a₁ = 2 ⇒ aₙ = Fₙ₊₂
Valid sequences
13
All sequences
32
Probability
13 / 32
= 0.40625 ≈ 40.63%
Fibonacci recurrence
The number of valid sequences is 1, 2, 3, 5, 8, 13, …
Example: n = 3
All 8 outcomes are equally likely.
TTT ✓
TTH ✓
THT ✓
THH ✗
HTT ✓
HTH ✓
HHT ✗
HHH ✗
P₃ = 5 / 8
Final result
# valid = Fₙ₊₂
÷
# total = 2ⁿ
P(no HH) = Fₙ₊₂ / 2ⁿ
Interview shortcut
Define aₙ as the number of valid length-n sequences. Split by the final toss.
If it ends in T, there are aₙ₋₁ choices. If it ends in H, the previous toss must be T,
so there are aₙ₋₂ choices. Hence aₙ = aₙ₋₁ + aₙ₋₂.
With a₀ = 1 and a₁ = 2, we get aₙ = Fₙ₊₂.