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

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

See The Solution Submitted by Ady TZIDON    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution 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      2
2   2     1      3
3   3     2      5
4   5     3      8
5   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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information