Probability recursion Im trying to find the recursive relation that find the probability that when tossing a coin over and over the pattern tth show for the first time on the nth trial.  I'm really stumped on this, I tried using the law of the total probability on the first outcome(head or tails ) to no avail and defining two events that tth doesn't appear in the first n trials and appears in the nth trial didn't work.  How is this done??
 A: Let $S$ denote the first time when the motive TTH is completed. To compute the distribution of $S$, one considers the Markov chain on the state space $\{0,1,2,3\}$ whose state at time $n$ is the length of the maximal initial subword of TTH which is at the end of the letters produced at time $n$. 
For example, if the initial letters are HTHHTTTHT, the first states of the Markov chain are $0010012231$. 
Note that $S$ is the first hitting time $\theta$ of state $3$ by this Markov chain hence one can compute $u_i=E_i(s^\theta)$ where the subscript $i$ means that one starts at state $i$. The usual one-step Markov recursion yields
$$
u_0=\tfrac12s(u_0+u_1),\quad u_1=\tfrac12s(u_0+u_2),\quad u_2=\tfrac12s(1+u_2),
$$
hence
$$
u_0=\frac{s^3}{(2-s)(4-2s-s^2)}.
$$
Now, $P[S=n]$ is the coefficient of $s^n$ in the power series $u_0$ hence one decomposes $u_0$ as
$$
u_0=1-\frac{2}{2-s}+\frac1{\sqrt5}\frac{a}{a-s}-\frac1{\sqrt5}\frac{b}{b+s},
$$
with $a=\sqrt5-1$ and $b=\sqrt5+1$. Thus, for every $n\geqslant3$,
$$
P[S=n]=[s^n]u_0=-\frac1{2^n}+\frac1{\sqrt5}\frac1{a^n}-\frac1{\sqrt5}(-1)^n\frac1{b^n}\sim\frac1{\sqrt5}\frac1{a^n}.
$$
A: This might help:  OEIS sequence A000071 counts "the number of 001-avoiding binary words of length $n-3$."
To expand on this, the probability of getting TTH for the first time on the $n$th toss is clearly ${1\over8}p(n-3)$, where $p(n-3)$ is the probability of avoiding TTH in a string of length $n-3$.  Now a TTH-avoiding string of length $k$ either starts with an H followed by a TTH-avoiding string of length $k-1$, with a TH followed by a TTH-avoiding string of length $k-2$, or consists solely of T's.  Thus
$$p(k)={1\over2}p(k-1)+{1\over4}p(k-2)+{1\over2^k}$$
where $p(0)=p(1)=1$ (from which the recursion gives $p(2)=1$ as well).  If we write $q(k)=2^kp(k)$, the recursion is $q(k)=q(k-1)+q(k-2)+1$, leading to the sequence $1,2,4,7,12,20,33,\ldots$ of OEIS A000071.  Writing $q(k)=f(k)-1$ gives $f(k)=f(k-1)+f(k-2)$, showing why the Fibonacci numbers play the role they do.
Added later:  Just for definiteness, let $P(n)$ denote the probability of getting TTH for the first time on the $n$th toss.  Then the recursion requested by the OP is precisely
$$P(n) = {1\over2}P(n-1)+{1\over4}P(n-2)+{1\over2^n}$$
where $P(1)=P(2)=0$, so that $P(3)={1\over8}$, $P(4)={1\over2}P(3)+{1\over16}={1\over8}$, $P(5)={1\over2}P(4)+{1\over4}P(3)+{1\over32}={1\over8}$, and so forth.  It's easiest to slip appropriate powers of $2$ under the terms of the OEIS sequence:
$${0\over2},{0\over4},{1\over8},{2\over16},{4\over32},{7\over64},{12\over128},{20\over256},{33\over512},{54\over1024},\ldots$$
