Given a fair coin, on average what is the number of tosses needed to get 3 heads in a row? My attempt:
Let $H$ be the outcome heads, and $T$ be tails. Let $X$ be the random variable "number of tosses required to get 3 consecutive heads". The minimum number of trials (tosses) is 3. Thus we have infinite sample space:
$$\{HHH, THHH, TTHHH, HTHHH, TTTHHH, THTHHH, HTTHHH, HHTHHH,....\}$$
For the first 2 elements of sample space, we have the probabilities $(1/2)^{3}$ and  $(1/2)^{4}$ respectively. Then we have 2 ways to get 3 consecutive heads out of 5 tosses, hence the probability is $2(1/2)^{5}$. Similar for 4th, 5th and 6th tosses. For $n = 7, 8, 9,... \infty$ tosses, we have 
$$2^{n-4} - \frac{(n-5)(n-6)}{2}$$
ways of getting 3 consecutive heads.
Thus the expectation is
$$E(X) = 3(1/2)^{3} + 4(1/2)^{4} + 5 \cdot 2 (1/2)^{5} + 6 \cdot 4(1/2)^{6} + \sum_{n=7}^{\infty}  \frac{n}{2^{n}}\left(2^{n-4} - \frac{(n-5)(n-6)}{2}\right) $$
However the infinite sum above doesn't converge, so obviously the approach is wrong.
I have looked at related posts (i.e. Expected Number of Coin Tosses to Get Five Consecutive Heads) but I don't see how my approach fails.
Edit: computation of $$2^{n-4} - \frac{(n-5)(n-6)}{2}, \qquad n \geq 7.$$
I need to compute the number of ways that X -values can be next to each other for a given number of tosses $n \geq 7$. For this $n$, I have a sample space element of the form $...TXXX$, consisting of $n$ symbols $T$ and $H$. Thus, I have a choice of $2^{n-4}$ arrangements for the first $n-4$ symbols. Out of those, I need to exclude the sequences of symbols of the form $XXX...X$, for 3 or more values of $X$. There are $(n-6)$ such arrangements for 3 consecutive $X$ values, $(n-7)$ arrangements for 4 consecutive $X$s, $(n-8)$ arrangements for 5 $X$s, and so on. Hence for the total of such arrangements, we have the arithmetic progression
$$n-6, n-7, n-8,...0.$$
For a given $n$, the sum turns out to be $$\frac{(n-5)(n-6)}{2}$$
Hence, we have the result $2^{n-4} - \frac{(n-5)(n-6)}{2}$ as stated above...
 A: Here is a standard trick for this kind of situation. It hinges on the fact that expectation satisfies a law similar to the law of total probability. You'll see what I mean below.
Let $A$ be the event "the first toss is a heads". Then we have
$$
E(X)=E(X\mid A)P(A)+E(X\mid \bar A)P(\bar A)\\
=\frac12E(X\mid A)+\frac12(1+E(X))
$$
since the expectation of $X$ given that the first toss is a tails is clearly one more than the expectation of $X$; you just wasted a throw.
Now, for $E(X\mid A)$, we can do a similar trick: let $B$ be the event "the second toss is a heads", and we get
$$
E(X\mid A)=E(X\mid A,B)P(B)+E(X\mid A,\bar B)P(\bar B)\\
=\frac12E(X\mid A,B)+\frac12(2+E(X))
$$
Finally, we must calculate $E(X\mid A,B)$. You can probably guess how: let $C$ be the event "the third toss is heads", and we get
$$
E(X\mid A,B)=E(X\mid A,B,C)P(C)+E(X\mid A,B,\bar C)P(\bar C)\\
=\frac12\cdot 3+\frac12(3+E(X))
$$
Since $A,B,C$ together means you succeeded to get three heads in a row on the first three throws, we must have $E(X\mid A,B,C)=3$.
Now you can just insert everything into the original equation, and solve for $E(X)$.
A: Let's define the states as the expected stopping time from given n consecutive Heads, i.e. $S_n = E\{\tau \mid \text{n consecutive H} \}$  
Starting with zero Heads, we can write transition recurrence equations. 
\begin{align}
  S_0 &= \frac12 S_0 + \frac12 S_1 + 1  \\
  S_1 &= \frac12 S_0 + \frac12 S_2 + 1  \\
  S_2 &= \frac12 S_0 + \frac12 S_3 + 1 
\end{align}
Note that $S_3=0$ by definition (we're done after $HHH$). From where you can solve $S_0$
A: Let $e_k$ $(0\leq k\leq2)$ be the expected number of additional tosses when we have $k$ heads "on the stock". We then have the following system of equations:
$$
e_0=1+{1\over2}e_0+{1\over2}e_1,\qquad
e_1=1+{1\over2}e_0+{1\over2}e_2,\qquad
e_2=1+{1\over2}e_0\ .$$
Solving gives $e_0=14$.
A: You are not subtracting off conditions like XXXTXXXTXXX, since you are only counting the variations where there is only 1 XXX. As n gets large, you incur an exponential penalty from all these cases you are ignoring.
A: The more general case of asking for the average number $E$ of rolls of a fair $X$-sided die ending with a run of $N$ consecutive heads is
answered in this MSE post as
\begin{align*}
E=\frac{X(X^N-1)}{X-1}\tag{1}
\end{align*}

Here we apply (1) by considering a coin as two-sided die ($X=2$) and tosses ending in heads with run-length $N=3$. We conclude the average number of trials is
  \begin{align*}
\color{blue}{E(X=2,N=3)=\frac{2\left(2^3-1\right)}{2-1}=14}
\end{align*}

