# Stats Proof - Tossing a coin

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?

• You really should include your own thoughts on the problem. Oct 18, 2016 at 0:29
• added my thoughts Oct 18, 2016 at 0:39

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}}$.