Let $T$ be the number of tosses required until three consecutive heads appear for the first time. Find $\textbf{E}(T)$. A fair coin is tossed repeatedly. Let $A_{n}$ be the event that three heads have appeared in consecutive tosses for the first time on the $n$-th toss. Let $T$ be the number of tosses required until three consecutive heads appear for the first time. Find $\textbf{P}(A_{n})$ and $\textbf{E}(T)$.
Let $U$ be the number of tosses required until the sequence $HTH$ appears for the first time. Can you find $\textbf{E}(U)$?
EDIT
The textbook provides an answer based on recurrence equations, but I seek for an alternative approach if it is possible. Can somebody please help me out? Thanks in advance.
 A: What follows is a well-known approach to computing the expectation of $T$. 
Consider the following gambling scheme: just before each time $n\in \mathbb{N}$ a new gambler arrives and bets $1$ \$ that the $n$-th outcome of the coin toss is $H$. If the bet is correct the gambler wins $2$ (since the coin is fair) and bets it, the $2$, on the next outcome to be $H$ as well. Again, if the gambler win, he bets the fortune of $4$ on the next toss to be $H$. Winning that also, ends the game and leaves him with a fortune of $8$. 
Now let $X_k^i$, where $k\geq 1$ and $i=1,2,3$ be the fortune of the $k$-th gambler after their $i$-th bet. For instance, the winner, if he was the $k$-th to enter the game, will have $X_k^1 = 2$, $X_k^2 = 2^2$ and  $X_k^3 = 2^3$, while for all gamblers who did not make to the third from the last move, $X_k^i = 0$ for each $i=1,2,3$.
Define 
$$
S_n = \sum_{\substack{k=1\\i=1,2,3\\ k + i \leq n + 1}}^n X_k^i 
$$
which is the total fortune of all gamblers after the $n$-th toss. Notice that exactly $n$ dollars were bet up to and including time $n$. Since the coin is fair and in view of our definition of $X_k^i$, it is easy to see that the sequence 
$$
M_n: = S_n - n
$$ 
is a martingale with respect to the natural filtration generated by $\{X_n\}_{n\in \mathbb{N}}$. Define 
$$
\tau = \inf\{n\in \mathbb{N}: \ X_{n-2} X_{n-1} X_n = H H H \},
$$
which is a stopping time, and defines the time when the game ends. We have $\mathbb{E}(\tau) <\infty$. Indeed, the probability of getting $HHH$ on tosses $3k, 3k+1,3k+2$ equals $1/8$, hence dividing the interval of integers $[1,...,3k]$ to length $3$ intervals, it follows that the probability of NOT getting $HHH$ up to time $3k$ is bounded above by $1/8^k$. Thus $\mathbb{P}(\tau > 3k) \leq 1/8^k$, hence the conclusion of $\mathbb{E}(\tau) < \infty$.  
Now, using the fact that $M_n$ has bounded increments and $\tau$ has fininte expectation, we apply the optional stopping theorem to get $\mathbb{E}M_\tau = 0 $, thus
$$
0 = \mathbb{E}M_\tau = \mathbb{E}  S_\tau  - \mathbb{E} \tau.
$$
But observe, that at the time of finishing the game, i.e. at time $\tau$, the only gamblers with non-zero fortunes are the winner, and the other two who entered the game at times $\tau-1$ and $\tau$ respectively. Each of these three gets $2^3$, $2^2$ and $2$, hence
$$
\mathbb{E} \tau = 2^3 + 2^2 + 2 = 14.
$$
For instance, using the same argument, it follows that for the pattern $HTH$, the expected time equals $2^3 + 2$.

See also this post for non-martingale approach to the above problem, which gives a combinatorial argument based on generator functions.

We can also get a formula for the probability of the event $A_n$. It was already mentioned in the other answer above that the event $A_n$ comprises of all sequence of length $n$ ending in $THHH$ and having at most $2$ consecutive $H$-s before time $n-4$.
Hence we need to compute the number of length $n$ sequences of $\{H,T\}$ with at most $2$ consecutive $H$. Denote this number by $a_n$.
Clearly $a_1 = 1$, $a_2 = 3 $, $a_3 = 5$. For $n>3$ we claim that
$$
\tag{1} a_n = a_{n-1} + a_{n-2} + a_{n-3}.
$$ 
Indeed, each such sequence of length $n$ either ends in $H$ or $T$. If it ends with $T$, we have length $n-1$ remaining which can end in both $H$ and $T$, hence $a_{n-1}$ of such contributions. For sequences ending with $H$, we continue tracking the $n-1$-th position: if it's $H$, then the $n-2$-th needs to be $T$, hence $a_{n-3}$ of these, otherwise, if it's $T$, we are free to choose the $n-2$-th, thus we get $a_{n-2}$.
Since the set $A_n$, sequences of length $n$ where $HHH$ appears for the first time on step $n$ has the following structure:
$$
\text{length } n-4 \ \text{sequences of at most } 2 \ \text{ Heads } \text{ followed by } THHH,
$$
it follows
$$
\mathbb{P}(A_n) = 2^{-n}a_{n-4},
$$
with $a_n$ as in $(1)$.
A: Let $e$ be the expected number of tosses.  Start tossing. If we get a tail immediately (probability $\frac{1}{2}$) then the expected number is $e+1$. If we get a head then a tail (probability $\frac{1}{4}$), then the expected number is $e+2$ If we get $2$ heads then a tail, the expected number is $e+3$. Finally, if our first $3$ tosses are heads, then the expected number is $3$. Thus
$$e=\frac{1}{2}(e+1)+\frac{1}{4}(e+2)+\frac{1}{8}(e+3)+\frac{1}{8}(3).$$
IF you solve the equation, you get $e = 14$.
Remark: emabraced the idea from Andre Nicolas's solution.
A: You can't have $P(A_n)=2^{-n}$ for $n \ge 3$ because the probabilities do not sum to $1$.  It is true that $P(A_3)=\frac 18$ because you need $HHH$ and $P(A_4)=\frac 1{16}$ because you need $THHH$, but $P(A_5)=\frac 1{16}$ because you win with both $TTHHH$ and $HTHHH$.  For $n \ge 5, A_n$ consists of a string of $n-4$ tosses that does not have three heads in a row followed by $THHH$.  If you count the probability that you can have $n-4$ tosses without three heads in sequence the chance of $A_n$ is $\frac 1{16}$ of this.
