You flip a fair coin 10 times. What is the probability that you never get two heads in a row?
Express as a fraction
Show solution
Let f(n) be the number of length-n binary strings with no two consecutive heads. We have f(1)=2, f(2)=3, and f(n)=f(n−1)+f(n−2) (the string starts with T followed by a valid (n−1)-string, or HT followed by a valid (n−2)-string). Computing: f(3)=5,f(4)=8,f(5)=13,f(6)=21,f(7)=34,f(8)=55,f(9)=89,f(10)=144. Out of 210=1024 total strings, the probability is 1024144=649.