This is a computational exercise, so think recursively. The current state of coin flipping is determined by the ordered pair $(N,M)$ with $N\ge M\ge 0$. Let the expected number of flips to reach $N$ consecutive heads be $e(N,M)$:
(1) There is a 50% chance the next flip will be heads, taking you to the state $(N,M+1)$, and a 50% chance the next flip will be tails, taking you to the state $(N,0)$. This costs one flip. Therefore the expectation (recursively) is given by
$$e(N,M) = \frac{1}{2} e(N,M+1) + \frac{1}{2} e(N,0) + 1.$$
(2) Base conditions: you have already stipulated that
$$e(N,0) = 2^{N+1}-2$$
and obviously
$$e(N,N) = 0$$
(no more flips are needed).
Here's the corresponding Mathematica program (including caching of intermediate results to speed up the recursion, which effectively makes it a dynamic programming solution):
e[n_, m_] /; n > m > 0 := e[n, m] = 1 + (e[n, m + 1] + e[n, 0])/2 // Simplify
e[n_, 0] := 2^(n + 1) - 2
e[n_, n_] := 0
The program would look similar in other programming languages that support recursion. Mathematically, we can verify that $e(N,M) = 2^{N+1} - 2^{M+1}$ simply by checking the recursion, because it obviously holds for the base cases:
$$2^{N+1} - 2^{M+1} = 1 + (2^{N+1} - 2^{M+2} + 2^{N+1} - 2)/2,$$
which is true for any $M$ and $N$, QED.
More generally, the same approach will establish that $e(N,M) = \frac{p^{-N} - p^{-M}}{1-p}$ when the coin has probability $p$ of heads. The hard part is working out the base condition $e(N,0)$. That is done by chasing the recursion out $N$ steps until finally $e(N,0)$ is expressed in terms of itself and solving:
$$\eqalign{
e(N,0) &= 1 + p e(N,1) + (1-p) e(n,0) \\
&= 1 + p\left(1 + p e(N,2) + (1-p) e(N,0)\right) + (1-p) e(N,0) \\
\cdots \\
&= 1 + p + p^2 + \cdots + p^{N-1} + (1-p)[1 + p + \cdots + p^{N-1}]e(N,0);\\
e(N,0) &= \frac{1-p^N}{1-p} + (1-p^N)e(N,0); \\
e(N,0) &= \frac{p^{-N}-1}{1-p}.
}$$
The first answer is correct. Let's say we flip a coin with bias $p$ (probability of heads) until it lands on heads, and the number of tosses is $X$. I'll demonstrate a more direct calculation and then you'll see why the recursive calculation works.
$$
\mathbb{E}[X] = 1p + 2p(1-p) + 3p(1-p)^2 + 4p(1-p)^3 + \dots
$$
This is because if $X = n$, there have been $(n-1)$ tails and then $1$ heads. Now let's try to relate this to your expression. We are going to add $1$ to both sides but on the right hands side it will be in a tricky form.
$$
1 = p + p(1-p) + p(1-p)^2 + \dots = P(1) + P(2) + + P(3) \dots
$$
So then we have,
$$
\mathbb{E}[X] + 1 = 2p + 3p(1-p) + 4p(1-p)^2 + 5p(1-p)^3 + \dots
$$
So if we multiply both sides by $(1-p)$ and add $p$ we have,
$$
p + (1-p)(\mathbb{E}[X] + 1) = p + 2p(1-p) + 3p(1-p)^3 + \dots = \mathbb{E}[X].
$$
That concludes the proof, but how about the intuition. The intuition is that when you start flipping, with probability $p$ you finish on one flip, so let's add
$$
1 \cdot p
$$
to the expectation. With probability $(1-p)$ you get a tails and pretty much start all over again, but of course you have wasted a flip. So we add
$$
(1-p)(1 + \mathbb{E}[X])
$$
to the expectation. Hope that helps. If you have any questions, please comment.
Best Answer
Let $T^{(k)}$ be the time it takes to see the first run of $k$ successes.
Let $X\sim\mathrm{Ber}(p)$ be independent of $T^{(k)}$ for every $k$. Then, $$ T^{(k)} = (T^{(k-1)}+1)\, X + (T^{(k-1)}+1+T^{(k)}) \, (1 - X) \, , $$ because, in words, if I see a success in the current trial, then the time to get $k$ consecutive successes is the time to get $k-1$ consecutive successes plus one (the current trial); but if I see a failure, the time to get $k$ consecutive successes is the time to get $k-1$ consecutive successes plus one (the current trial), plus itself, because the process restarted in distribution.
Defining $a_k=\mathrm{E}[T^{(k)}]$, we find the recurrence $$ a_k = (a_{k-1}+1)\,p + (a_{k-1}+1+a_k)\,(1-p) \, , $$ or $$ a_k = \frac{a_{k-1}}{p}+\frac{1}{p} \, . $$