No Run of Two Heads

Solution

Let H(n) be the number of ways of flipping n coins in a row, never getting two heads in a row and ending with a head. Let T(n) be the number of ways of flipping n coins in a row, never getting two heads in a row and ending with a tail.

To start with:

H(1) = 1
T(1) = 1
H(2) = 1 (it can only by TH)
T(2) = 2 (can be HT or TT)

Let's establish some recurrences. First of all:

T(n+1) = T(n) + H(n)

since we can add a tail to any sequence ending with a head or a tail.

H(n+1) = T(n)

since we can only add a head to a sequence ending with a tail. Hence:

H(n+1) = T(n) = T(n-1) + H(n-1) = H(n) + H(n-1)

Together with H(1) = H(2) = 1, this establishes that H(n) is the nth Fibonacci number, so:

H(100)	=	F(100) / 2100
	=	316912650057057350374175801344 / 2100