Expected number of tosses of getting $n$ heads in a row I'm looking at a proof by induction of getting $n$ heads in a row, and I'm not understanding what law they are using in this proof.
To start, let's define $f(n)$ as the number of tosses needed to get $n$ heads in a row. The formula is given to be $E[f(n)] = 2^{n+1} - 2$, and we are asked to prove this formula by induction. 
The step I am getting lost is where they assume this formula holds for $n=k$ and use this to show that it holds for $n=k+1$. The notes wrote that "Conditioned on the previous state (k heads in a row), there is a 0.5 probability it will toss another head and thus go to the state with k+1 heads in a row and the process stops, or if it tosses a tail, with probability 0.5, it goes to the starting state. Therefore 
$$
E[f(k+1)] = E[f(k)] + 0.5*1 + 0.5E[f(k+1)]
$$
.
I don't understand where this equation came from. It seems to be a form of the law of total expectation, but it's not clear to me what the conditional events are.
The way I learned law of total expectation is the following:
$$
E[X] = \sum_i E[X|A_i] P(A_i)
$$
for disjoint events $A_i$. What are the $A_i$'s in this problem? Is it (1) Starting from k heads in a roll and tossing a head (2) starting from k heads in a roll and tossing a tail? 
So something like the following?
$$
E[f(k+1)] = E[f(k+1) | \kappa, T]P(\kappa, T) + E[f(k+1) | \kappa, H]P(\kappa, H)
$$
where $\kappa$ is the event of having $k$ heads in a row, and $T$ and $H$ are the events tossing a tail and a head.
 A: To get $k + 1$ heads in a row, you first need to get $k$ heads in a row.
By definition, in $f(k)$ tosses, you get $k$ heads in a row, so $f(k + 1) - f(k)$ is the number of tosses between getting $k$ heads and getting $k + 1$ heads.
There are two possibilities for the $(f(k) + 1)$-th toss, head or tail. These are the two disjoint events you are looking for. We denote them by $H$ and $T$.
Using the formula of total expectation, we will have $$E[f(k + 1) - f(k)] = E[f(k + 1) - f(k)|H] \times 0.5 + E[f(k + 1) - f(k)|T] \times 0.5.$$
Now if $H$ happens, then we obviously have $f(k + 1) - f(k) = 1$, hence $E[f(k + 1) - f(k)|H] = 1$.
If $T$ happens, then the first $f(k) + 1$ tosses are all wasted, so that $E[f(k + 1) - (f(k) + 1)|T] = E[f(k + 1)]$.
Hence we get $$E[f(k + 1)] = E[f(k)] + 1 \times 0.5 + (1 + E[f(k + 1)]) \times 0.5.$$ This is slightly different from the formula in your question. I doubt that it's a typo in your source material.
Solving this recurrence relation gives us the willing result.
