How many sequences of coin flips of length $$n$$ do not contain $$HH$$? E.g. there are 5 for $$n = 3: TTT, TTH, THT, HTT, HTH$$.

· · Web · · ·

@alexdbolton this is one of those problems that seem much easier to brute force with a computer than to figure out by hand.

Spoilers for maths problem

@alexdbolton just playing around with this, and I think the answer is: fibonacci sequence! There are 2 1-flip sequences, 3 2-flip sequences, 5 3-flip sequences and so on...

Spoilers for maths problem

@alexdbolton quick proof: if there are t (n-1) filp sequences that end in a T and h (n-1) flip sequences that end H, then there are h+t n-flip sequences that end in a T and there are t n-flip sequences that end in a H. (since the only way to end in an H is to have a T in the penultimate slot.)

@alexdbolton Nice! I wasn't expecting that when I started off.

@alexdbolton reminds me of my baby's stacking cups: youtu.be/vS2i0h7IL5U

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!