<s>[INST] How many possibilities are there for at least $k$ consecutive heads to show up out of $n$ tosses? Consider $n$ coin tosses. In how many ways can we have at least $k$ consecutive heads? Call this number $f(n,k)$. Is there a general expression for it? Or at least tight upper and lower bounds?
For example take $n=5,k=2$. Then the possibilities are: 
HHTTT, THHTT, TTHHT,TTTHH,
HHHTT, HHTHT, HHTTH, THHHT, THTHH, THHTH, HTHHT, TTHHH, HTTHH,
HHHHT, HHHTH, HHTHH, HTHHH, THHHH,
HHHHH.
that is 19 ways
 [/INST] 
We consider the binary alphabet $V=\{H,T\}$. We are looking for the number $g(n,k)$  of strings of length $n$ having runs of $H$ at most length $k-1$. The wanted  number is  $$f(n,k)=2^n-g(n,k)$$

Strings with no consecutive equal characters at all are called Smirnov or Carlitz words. See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information. 
A generating function for the number of Smirnov words over a binary alphabet is given by
\begin{align*}
\left(1-\frac{2z}{1+z}\right)^{-1}\tag{1}
\end{align*}
Replacing occurrences of $H$ in a Smirnov word by one up to $k-1$ $H$ generates words having runs of $H$ with length less than $k$.
\begin{align*}\
z\longrightarrow z+z^2+\cdots+z^{k-1}=\frac{z\left(1-z^{k-1}\right)}{1-z}\tag{2}
\end{align*}
Since there are no restrictions to the length of runs of $T$'s we replace occurrences of $T$ in a Smirnov word by one or more $T$s.
\begin{align*}\
z\longrightarrow z+z^2+\cdots=\frac{z}{1-z}\tag{3}
\end{align*}

The resulting generating function is by substituting (2) and (3) in (1)
  \begin{align*}
\left(1- \frac{\frac{z\left(1-z^{k-1}\right)}{1-z}}{1+\frac{z\left(1-z^{k-1}\right)}{1-z}}-\frac{\frac{z}{1-z}}{1+\frac{z}{1-z}}\right)^{-1}
&=\frac{1-z^k}{1-2z+z^{k+1}}
\end{align*}
Denoting with $[z^n]$ the coefficient of $z^n$ in a series we obtain the number of wanted words of length $n$ as
  \begin{align*}
\color{blue}{f(n,k)}&=2^n-g(n,k)\\
&\color{blue}{=[z^n]\left(\frac{1}{1-2z}-\frac{1-z^k}{1-2z+z^{k+1}}\right)}
\end{align*}

Example: Let's look at OPs example. We take $k=2$. We obtain with some help of Wolfram Alpha
\begin{align*}
\frac{1}{1-2z}-\frac{1-z^2}{1-2z+z^{3}}=z^2+3 z^3 + 8z^4+\color{blue}{19} z^5 + 43 z^6 +\cdots
\end{align*}
The blue colored coefficient of $z^5$ shows there are $\color{blue}{19}$ words of length $5$ built from characters $\{H,T\}$ and runs of $H$ with length at least $k=2$ in accordance with OP's result.
</s>