We can derive an explicit formula of the probability $P(N,k)$ based upon the Goulden-Jackson Cluster Method.
We consider the set of words $\mathcal{V}^{\star}$ of length $N\geq 0$ built from an alphabet $$\mathcal{V}=\{H,T\}$$ and the bad word $\underbrace{HH\ldots H}_{k \text{ elements }}=:H^k$ which is not allowed to be part of the words we are looking for. We derive a function $f_k(s)$ with the coefficient of $s^N$ being the number of wanted words of length $N$.
The wanted probability $P(N,k)$ can then be written as
\begin{align*}
P(N,k)=1-\frac{1}{2^N}[s^N]f_k(s)
\end{align*}
According to the paper (p.7) from Goulden and Jackson the generating function $f_k(s)$ is
\begin{align*}
f_k(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\tag{1}
\end{align*}
with $d=|\mathcal{V}|=2$, the size of the alphabet and with $\mathcal{C}$ the weight-numerator with
\begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[H^k])
\end{align*}
We calculate according to the paper
\begin{align*}
\text{weight}(\mathcal{C}[H^k])&=-\frac{s^k}{1+s+\cdots+s^{k-1}}=-\frac{s^k(1-s)}{1-s^k}
\end{align*}
We obtain the generating function $f(s)$ for the words built from $\{H,T\}$ which don't contain the substring $H^k$
\begin{align*}
f_k(s)&=\frac{1}{1-2s+\frac{s^k(1-s)}{1-s^k}}\\
&=\frac{1-s^k}{1-2s+s^{k+1}}\tag{2}\\
\end{align*}
$$ $$
Note: For $k=2$ we obtain
\begin{align*}
f_2(s)&=\frac{1-s^2}{1-2s+s^{3}}\\
&=1+2s+3s^2+5s^3+8s^4+13s^5+21s^6+34s^7+\mathcal{O}(s^8)
\end{align*}
The coefficients of $f_2(s)$ are a shifted variant of the Fibonacci numbers stored as A000045 in OEIS.
Note: For $k=3$ we obtain
\begin{align*}
f_3(s)&=\frac{1-s^3}{1-2s+s^{4}}\\
&=1+2s+4s^2+7s^3+13s^4+24s^5+44s^6+81s^7+\mathcal{O}(s^8)
\end{align*}
The coefficients of $f_3(s)$ are a shifted variant of the so-called Tribonacci numbers stored as A000073 in OEIS.
$$ $$
We use the series representation of $f_k(s)$ in (2) to derive an explicit formula of the coefficients.
\begin{align*}
[s^N]f(s)&=[s^N](1-s^k)\sum_{m=0}^{\infty}(2s-s^{k+1})^m\\
&=[s^N](1-s^k)\sum_{m=0}^{\infty}s^m(2-s^k)^m\\
&=[s^N](1-s^k)\sum_{m=0}^{\infty}s^m\sum_{j=0}^m\binom{m}{j}(-1)^js^{kj}2^{m-j}\\
&=([s^N]-[s^{N-k}])\sum_{m=0}^{\infty}s^m\sum_{j=0}^m\binom{m}{j}(-1)^js^{kj}2^{m-j}\tag{3}\\
&=\sum_{m=0}^{N}([s^{N-m}]-[s^{N-k-m}])\sum_{j=0}^m\binom{m}{j}(-1)^js^{kj}2^{m-j}\tag{4}\\
&=\sum_{{m=0}\atop{m\equiv N(\bmod k)}}^{N}\binom{m}{\frac{N-m}{k}}(-1)^{\frac{N-m}{k}}2^{m-\frac{N-m}{k}}\\
&\qquad-\sum_{{m=0}\atop{m\equiv N(\bmod k)}}^{N-k}\binom{m}{\frac{N-m}{k}-1}(-1)^{\frac{N-m}{k}-1}2^{m-\frac{N-m}{k}+1}\\
&=\sum_{{m=0}\atop{m\equiv N(\bmod k)}}^{k-1}\binom{m}{\frac{N-m}{k}}(-1)^{\frac{N-m}{k}}2^{m-\frac{N-m}{k}}\tag{5}\\
&\qquad+\sum_{{m=k}\atop{m\equiv N(\bmod k)}}^{N-k}
\left(\binom{m}{\frac{N-m}{k}}-\frac{1}{2^k}\binom{m-k}{\frac{N-m}{k}}\right)(-1)^{\frac{N-m}{k}}2^{m-\frac{N-m}{k}}\\
\end{align*}
Comment:
In (3) we use the linearity of the coefficient of operator and $[s^N]s^mf(s)=[s^{N-m}]f(s)$
In (4) we change the limit of the left hand sum from $\infty$ to $N$ according to the maximum coefficient $[s^N]$. According to the factors $s^{kj}$ we consider in the following only summands with $m\equiv N(\bmod k)$
In (5) we reorganise the sums from the line above by extracting from the left hand sum the first summand and shifting in the right hand side the index by one and putting both sums together.
We conclude: An explicit representation of the probability $P(N,k)$ $(n\geq 0)$ is according to (5)
\begin{align*}
P(N,k)&=1-\sum_{{m=0}\atop{m\equiv N(\bmod k)}}^{k-1}\binom{m}{\frac{N-m}{k}}(-1)^{\frac{N-m}{k}}2^{-\frac{(k+1)(N-m)}{k}}\\
&\qquad-\sum_{{m=k}\atop{m\equiv N(\bmod k)}}^{N-k}
\left(\binom{m}{\frac{N-m}{k}}-\frac{1}{2^k}\binom{m-k}{\frac{N-m}{k}}\right)(-1)^{\frac{N-m}{k}}2^{-\frac{(k+1)(N-m)}{k}}
\end{align*}
I ask you for additional explanation. Meanwhile I'll post here another approach.
Denote by $\tau_i^5$ the random variable that counts the time required to get five heads starting from $i$ heads, ok?
What we want is exactly $E[\tau_0^5]$, right?
Now, you can evaluate $E[\tau_0^5]$ conditioning at the first step.
$$
E[\tau_0^5] = \frac{E[\tau_0^5]}{2} + \frac{E[\tau_1^5]}{2} +1
$$
Explaining the equation above. With probability $1/2$ you have a tail, so the time you will take to get five heads is the same, because you have any heads. On the other hand, with the same probability you get a head, and now, the number of flips needed to get 5 heads is $E[\tau_1^5]$, because now you that you have one head. The +1 it is because you have to count the first step.
Repeating the argument above you get
$$
E[\tau_1^5] = \frac{E[\tau_0^5]}{2} + \frac{E[\tau_2^5]}{2} +1
$$
Proceeding this way, and remembering $E[\tau_5^5]=0$, you get
$$
E[\tau_0^5] = 62
$$
This may seems more complicated at the first sight, but the idea of "to conditionate at what happens at the first time (or movement)" solve a big variety of problems.
Best Answer
If $n$ is large, the chance of a run of $n$ heads is very small, $2^{-n}$. We can view each flip as a try by me to start a run of $n+1$ heads, which happens with probability $2^{-(n+1)}$ and a try by you to start a run of $n$ heads, which happens with probability $2^{-n}$. Almost all flips will fail for both of us. We can ignore those. The chance that I win is then $\frac {2^{-(n+1)}}{2^{-n}+2^{-(n+1)}}= \frac{\frac 12}{1+ \frac12} = \frac 13$. The reason it starts lower is that we might both start a run at the same time, at which point you win because your run finishes first.