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??

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