The Numberphile video. What Simon is counting are Smirnov words with bounded runs. This blog gives the generating function to get these numbers, but in the part of direct counting it does not provide a way. This is what I am looking for.
Fortunately, this same blog suggests a way to get these words: we start with the Smirnov words (which in the binary case are very simple) with size $\le n$ and repeat some characters until we get a word of size $n$, taken care of not getting runs of 1 or 0 longer than $k$. In this way, we can relate the number of binary words without runs of more than $k$ with integer solutions of equations like $$ x_1+\ldots+x_j = m $$ with $0\le x_i< k-1$. The number of these can be obtained with the inclusion exclusion formula. Finally, with a bit of rearranging we arrive to the following formula $$ 2\sum_{a=0}^{\left\lfloor\frac{n-1}{k}\right\rfloor} (-1)^a \sum_{l=1}^{n-ak} \binom{l}{a}\binom{n-1-ak}{l-1}~~.\tag{1}$$ Note that the first term is $2^n$. I wonder if $(1)$ can be simplified further. With $n=20$ and $k=3$, expression $(1)$ predicts 242830, consistent with the video (at 6:19). There is also an additional calculation done in the video, counting the words with a single run of $4$ ones or zeroes. What is a formula for that calculation?