<s>[INST] Consecutive strings of heads problem So the question asks: 
We toss a fair coin $n$ times and record the outcome as a sequence of H and T. We say that there is a run of heads if there is a consecutive string H...H which starts either at the first toss or after the coin lands tails and which ends either at the last toss or before the coin lands tails. For example, the sequence HTHHTHHHHTTHH has four runs of heads. Find the expected number of runs of heads.
So far I have: 
Suppose the probability that all $K$ tosses have the same type of toss equal to the probability of all heads in $K$ tosses + probability of all tails in $K$ tosses.
Sets of subsequent $K$ tosses $=(n-k+1)$
Expected number of runs of heads equals the number of subsequent $K$ tosses times the probability that one set of $K$ tosses is a streak $= (n-k+1)\times 2\times (1/2)^k$
But I am really not sure about my solution, is this the right way to do this kind of probability problem? 
 [/INST] With  $z$  representing tails  and  $w$  representing  heads and  $u$
counting runs we get the generating function
$$\frac{1}{1-z}
\left(\sum_{q\ge 0} 
\left(u \frac{w}{1-w} \frac{z}{1-z}\right)^q\right)
\left(1+u\frac{w}{1-w}\right).$$
Actually we  are not interested  in the distinction between  heads and
tails once runs have been counted so we may use
$$\frac{1}{1-z}
\left(\sum_{q\ge 0} 
\left(u \frac{z^2}{(1-z)^2}\right)^q\right)
\left(1+u\frac{z}{1-z}\right).$$
This is
$$\frac{1-z+uz}{(1-z)^2} \frac{1}{1-uz^2/(1-z)^2}
= (1-z+uz) \frac{1}{(1-z)^2 - uz^2}.$$
Note that putting $u=1$ we obtain
$$\frac{1}{1-2z}$$
which is good news because it shows we have counted all strings.

Now for the expected number  of runs differentiate with respect to $u$
and set $u=1$ first getting
$$\frac{z}{(1-z)^2 - uz^2}
- (1-z+uz) \frac{1}{((1-z)^2-uz^2)^2} (-z^2).$$
and then
$$\frac{z}{1-2z}
+ \frac{z^2}{(1-2z)^2}
= \frac{z(1-2z)+z^2}{(1-2z)^2}
= \frac{z-z^2}{(1-2z)^2}.$$
We thus get for the expectation
$$\frac{1}{2^n} [z^{n-1}] \frac{1}{(1-2z)^2}
- \frac{1}{2^n} [z^{n-2}] \frac{1}{(1-2z)^2}
\\ = \frac{1}{2^n} n 2^{n-1} 
- \frac{1}{2^n} (n-1) 2^{n-2}
= \frac{1}{2} n - \frac{1}{4} (n-1)
= \frac{1}{4} (n+1).$$
</s>