All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Coin flips (Posted on 2014-01-10)
How many sequences of coin flips of length n have no appearance of 2 or more heads in a row?

Comments: ( Back to comment list | You must be logged in to post comments.)
 An old Friend (spoiler) Comment 1 of 1
Let T(n) be the number of sequences of length n that end with Tails and do not have 2 consecutive heads.
Let H(n) be the number of sequences of length n that end with Heads and do not have 2 consecutive heads.
Let G(n) be the total number of sequences, ie. T(n) + H(n)

We can form an acceptable sequence of length n + 1 in one of two ways:

By adding a Tail to the end of any acceptable sequence of length n.
By adding a Head to the end of any acceptable sequence of length n that ends in Tails.

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

initial conditions are
T(1) = 1  (only sequence is T)
H(1) = 1  (only sequence is H)

So, the table looks as follows:

`n  T(n)  H(n)  G(n)-- ---   ---   -----1   1     1      22   2     1      33   3     2      54   5     3      85   8     5     13`

So, all the sequences are Fibonacci, F(n)!

H(n) = F(n)
T(n) = F(n+1)
G(n) = F(n+2)

 Posted by Steve Herman on 2014-01-10 11:05:35

 Search: Search body:
Forums (0)