Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Let $f_n$ be the number of ways of tossing a fair coin $n$ times so that two consecutive heads never appear.
Prove that $f_n = f_{n-1}+f_{n-2}$ and thereby determine $f_n$.
What is the probability that two consecutive heads will not appear in $n$ tosses of a fair coin?
My thoughts on the question: - really have no idea where to begin. Do you use binomial distribution to solve this since you want $n$ successes out of $x$ tries?
Consider the last toss. If head, the one before the last must be a tail and the number of ways to form the rest of the sequence is $f(n-2)$. If tail, the rest of the sequence can be formed in $f(n-1)$ ways, because this last toss doesn't matter. The latter means that $f(n) = f(n-1)+f(n-2)$. Seeing also that $f(1)=2$ which is the third Fibonacci number and $f(2)=3$ which is the fourth Fibonacci number, we get to the answer $f(n)=F_{n+2}$, e.g. the $n-2$ Fibonacci number. The corresponding probability will be $\frac{F_{n+2}}{2^{n}}$.
