I have a problem with one exercise from Probability and Random Processes (2001) by Geoffrey R. Grimmett and David R. Stirzaker.
A coin shows heads with probability $p$. Let $X_n$ be the number of flips required to obtain a run of n consecutive heads. Show that $E(X_n) = \sum\limits_{i=1}^n p^{-i}$.
The solution offered by authors is
$E(X_n) = E\{E(X_n|X_{n-1})\} = E\{p(X_{n-1} + 1) + (1-p)(X_{n-1} + 1 + X_{n})\}$.
I am a bit confused with the last equation.
From definition of $E(X|Y)$ we shoud have something like: $$ E(X_n|X_{n-1}) = \begin{cases} v_1, \text{with} \; \text{probability} \; P(X_{n-1} = w_1), \\ v_2, \text{with} \; \text{probability} \; P(X_{n-1} = w_2), \\ \dots \end{cases} $$ But on the right hand we got something like this (from answer to Rigorous proof of the recursion method to compute expectations in probability.) $$ E(X_n) = E(X_n|X_n \; \text{ends})P(X_n \; \text{ends}) + E(X_n|X_n \; \text{starts} \; \text{again})P(X_n \; \text{starts} \; \text{again}) $$
So could someone expand the given answer in a more clear and strict form.
Excuse my English, I'm not a native speaker.
Let $E_i=E[X_i]$ for convenience.
The idea is to wait until you have thrown $n-1$ Heads for the first time. Then, you either get $H$ on the next toss (in which case you are done) or you throw $T$ in which case you start over. Since you expect it to take $E_{n-1}$ tosses to get that string of $n-1$ $H's$ we get the recursion $$E_n=p(E_{n-1}+1)+(1-p)(E_n+E_{n-1}+1)$$
After all, if you do get $H$ as the next toss after the $n-1$ Heads, then you expect it to have taken $E_{n-1}+1$ tosses. If you get a $T$ instead then you expect to have thrown $E_{n-1}+1$ times and you have to start over, so you expect to need another $E_n$ throws.
Thus $$E_n=1+E_{n-1}+(1-p)E_n\implies pE_n=1+E_{n-1}\implies E_n=\frac 1p+\frac 1p\times E_{n-1}$$
Starting with $E_0=0$ (or with $E_1=\frac 1p$ if you prefer) we get the desired result by induction.