Probability of getting "tails-tails" for the first time. 

A fair coin is tossed until the coin lands "tails-tails" (i.e. a tails followed by a tails) for the first time. Let $X$ counts the number of tosses required. Find the probability of the event $X=n.$  What will be the expectation of $X$?


I think this problem has to be solved by recursion but I find difficulty to solve this. Any suggestions regarding this will be highly appreciated.
Thank you very much for your valuable time.
EDIT $:$  If got "tails-tails" for the first time in $n$ steps. Then the first two steps will be either $HH$ or $HT$ or $TH.$ If the first two tosses will yield either $HH$ or $TH$ then we follow the previous step. If it yields $HT$ in the first two steps then the next two steps will be either $HH$ or $HT$ and we go on like that.
We know that $\Bbb E(X) = \Bbb E(X \mid A) \Bbb P(A) + \Bbb E(X \mid A^c) \Bbb P(A^c).$
So in this case we can write $\Bbb E(X) = \Bbb E(X \mid H) \Bbb P(H) + \Bbb E(X \mid T) \Bbb P (T).$
Now $$\Bbb E(X \mid H) = \Bbb E(X) + 1, \Bbb P(H) = \frac 1 2.$$ What is $\Bbb E(X \mid T)$? $$\Bbb E(X \mid T) = \Bbb E((X  \mid T) \mid TH) \Bbb P (TH \mid T) + \Bbb E((X \mid T) \mid TT) \Bbb P(TT \mid T).$$ Now $$\Bbb E((X  \mid T) \mid TH) = 1 + \Bbb E(X \mid H) = 2 + \Bbb E(X).$$ and $$\Bbb E((X \mid T) \mid TT) = 2.$$ Also $$\Bbb P(TH \mid T) = \Bbb P(TT \mid T) = \frac 1 2.$$ So we get $$\Bbb E (X \mid T) = \frac 1 2 \Bbb E(X) + 2.$$ Putting all these together we get $\Bbb E(X) = 6.$ 
Where have I done mistake? Would you please check it?
 A: Hints:
Let $g_n$ be the number of sequences of length $n$ made up of $H$ and $T$ (heads and tails) that contain no two consecutive tails. Then the sequence you want is such a sequence (but of length $n - 2$) followed by $TT$. Assume you know the value of $g_n$ in general. In terms of $g_{n - 3}$, what is the desired probability?
Now, to compute $g_n$, consider how we can obtain a such a sequence of length $n$ from a similar sequence of smaller length. Suppose you're given a sequence of length $n - 1$ that contains no $TT$ (two consecutive tails). Then definitely we can add an $H$ to the end of this sequence to get a valid sequence of length $n$? How many such sequences are there (in terms of the unknown $g_k$)? Does this not count all valid sequences ending in $H$?
So that leaves valid sequences of length $n$ ending in $T$. How shall we get such a sequence? Well, if the last term is $T$, then certainly the term before that must be $H$ (for otherwise we would have $TT$ at the end). So what we want is a valid sequence of length $n - 1$ that ends in $H$. How many such sequences are there (again in terms of the unknown $g_k$)?
Adding the above two should give a recurrence relation for $g_n$. The base cases are $g_0 = ???$ and $g_1 = ???$.
You can also easily convert this into a recurrence relation for the desired probability itself.

Full Solution:
The recurrence relation for $g_n$, the number of $H$-$T$ sequences of length $n$ that contain no $TT$ (consecutive tails)$ is
$$g_n = g_{n - 1} + g_{n - 2};\ g_0 = 1,\ g_1 = 2.$$
A sequence of length $n$ that ends in $TT$ and has no two consecutive tails before that is of the form $G_{n-3}HTT$, where $G_{n-3}$ is a sequence of length $n - 3$ with no consecutive tails. The probability of a sequence of $n$ tosses ending in $TT$ at the last two tosses for the first time is therefore
\begin{align*}
p_n & = \dfrac{g_{n-3}}{2^n}\\
& = \dfrac{g_{n-4} + g_{n-5}}{2^n}\\
& = \dfrac {p_{n-1}} 2 + \dfrac {p_{n-2}} 4
\end{align*}
with base cases $p_2 = \dfrac 1 4$, $p_3 = \dfrac 1 8$.
Then the expected number of tosses is $\sum\limits_{n = 2}^\infty n\, p_n$. To compute this using the recurrence relation that we already have for $p_n$,
\begin{align*}
n p_n &= \dfrac n 2 p_{n - 1} + \dfrac n 4 p_{n - 2} \\
&= \dfrac {1} 2 (n - 1) p_{n - 1} + \dfrac 1 2 p_{n-1}  + \dfrac{1} 4 (n - 2)p_{n - 2} + \dfrac 2 4 p_{n-2}
\end{align*}
Now, we sum this up from $n = 4$ to $\infty$. Note that $\sum p_n = 1$. Thus,
\begin{align*}
\mathbb E[X] - 3 p_3 - 2 p_2 &= \dfrac 1 2 (\mathbb E[X] - 2 p_2) + \dfrac 1 2 (1 - p_2) + \dfrac 1 4 \mathbb E[X] + \dfrac 1 2 \implies\\
\mathbb E[X] &= 6.
\end{align*}
A: Let $h(n)$ denote the number of sequences of length $n$ that end with $H$ and don't contain $TT$. Since $h(n) = h(n-1)+h(n-2)$ and the base cases of $h(n)$ are $h(1) = 1$ and $h(2) = 2$, this is the Fibonacci sequence, $$h(n) = \frac{({\frac{1+\sqrt{5}}{2}})^{n+1}-{(\frac{1-\sqrt{5}}{2}})^{n+1}}{\sqrt{5}}$$
On another track,
$$\Bbb P(X = n) = \frac{h(n-2)}{2^{n}}$$. Plugging the explicit formula of $h(n)$ into the above probability and simplifying finds that $$\Bbb P(X = n) = \frac{({\frac{1+\sqrt{5}}{4}})^{n-1}-{(\frac{1-\sqrt{5}}{4}})^{n-1}}{2\sqrt{5}}$$ Using two infinite arithmetico-geometric sums, the expected value is found to be 6. Note: the expected value could also be found by Ned's method in an earlier comment of $E = \frac{1}{2}*(E+1)+\frac{1}{4}*(E+2)+\frac{1}{4}*2$. Solving for $E$ finds that $E = 6$.
