Probability that no two consecutive heads occur? 
A fair coin is tossed $10$ times. What is the probability that no two
  consecutive tosses are heads?

Possibilities are (dont mind the number of terms):
$H TTTTTTH$, $HTHTHTHTHTHTHT$.
But except for those,
let $y(n)$ be the number of sequences that start with $T$
$T _$, there are two options, $T$ and $H$ so,
$y(n) = y(n - 1) + x(n-1) = y(n - 1) + y(n - 2)$
Let $x(n)$ be the number of sequences that start with $H$, 
$H _$ the next option is only $T$ hence,
$x(n) = y(n - 1)$ 
The total number of sequences $F(n)$ is:
$$F(n) = y(n) + x(n) = 2y(n - 1) + y(n - 2)$$
We are after $F(10)$,
$$F(10) = 2y(9) + y(8)$$
$$F(3) = 2y(2) + y(1) = 1 + 4 = 5$$
$$F(4) = 2y(3) + y(2) = 6 + 2 = 8$$
But I'm not quite sure where this will take me though. 
 A: Let $f(n)$ be the noumber of sequences without two consecutive $H$, you want $\frac{f(10)}{2^{10}}$.
$f(1)=2$ and $f(2)=3$ by inspection.
We obtain the recursion $f_n=f_{n-1}+f_{n-2}$ why? every sequence of length $n$ without consecutive $H$ can be obtained uniquely by taking a sequence of length $n-2$ and adding $TH$ or by taking a sequence of length $n-1$ and adding $T$ at the end.
Using this we have $f(3)=5,f(4)=8,f(5)=13,f(6)=21,f(7)=34,f(8)=55,f(9)=89$ $f(10)=144$
So we want $\frac{144}{2^{10}}\approx0.14$
A: $F (n)$ is in fact a fibonacci sequence:
\begin{align}
F (n+1) &= 2 y (n) + y (n-1)\\
&= 2 [y (n-1) +y (n-2)] + y (n-2) + y (n-1)\\
&= 2 y (n-1) + y (n-2) + 2 y(n-2) +y (n-3)\\
&= F (n) +F (n-1)\\
\end{align}
Now $F (1) = |\{H,T\}|=2$ 
And $F (2) = |\{HT,TH,TT\}|=3$
So $ F (10) = 144$
There are $ 2^{10}=1024$ possible events.
Thus the required probability is $\frac {144}{1024} $.
A: With N coin tosses, there are $F_{N+2}$ different possible outcomes such that there are no two consecutive heads. $F_N$ is the $N_{th}$ Fibonacci number.
$F_1=1, F_2=1, F_3=2,\cdots$
The are $2^N$ all possible outcomes for N tosses.
Therefore the asked probability is $\frac{F_{12}}{2^{10}} = \frac{144}{1024}$
A: Denote the probability that no two consecutive tosses are heads in a sequence of $n$ tosses with $F(n)$. In addition, denote the probability that such a sequence ends with $H$ and $T$ with $F_H(n)$ and $F_T(n)$ respectively, such that $F(n) = F_H(n) + F_T(n)$.
If a sequence ends in $H$, then we cannot append another $H$ into the end, but all other combinations are valid. Hence,
$$\begin{equation}\begin{aligned}
F_H(n) &= \frac{1}{2} F_T(n-1), \\
F_T(n) &= \frac{1}{2} F_H(n-1) + \frac{1}{2} F_T(n-1).
\end{aligned}\end{equation}$$
We have $F_H(2) = \frac{1}{4}$ and $F_T(2) = \frac{1}{2}$ by inspection, and you can find the result by applying the recurrence relation repeatedly. You may also use matrix multiplication if that's your thing.
>>> X = np.array([[0, 0.5], [0.5, 0.5]])
>>> np.linalg.matrix_power(X, 8).dot([0.25, 0.5]).sum()
0.140625

The result is $0.140625$, i.e. $\frac{144}{1024}$.
