Generating function for number of words with no k consecutive 0's?

Question

I am trying to determine the generating function for the sequence $a_n$, where $a_n $ is the number of words of length n over the alphabet {0, 1, 2, ..., q-1} that do not contain the subword $0^k$.

I came up with the recurrence $a_{n+k} = sum_{i=n}^{i+k-1} (q-1)a_i$ for n $\geqslant$ k. And, I know that $a_i = q^i$ for 0 $\leqslant$ i $<$ k.

I actually got an answer for the generating function, but it is so ugly that I don't believe it could be the correct answer to the problem. I did it over again and got the same answer, so either I am making a mistake somewhere along the way or it is correct.

I am curious if someone else could give it a go and see if it turns out to be a very complicated answer for them as well.

This is the answer I got, I'm not sure how to format it nicely so it will be hard to follow:

$(1/(1-k(q-1)x^k))[((1 - (q x)^k)/(1 - q x)) (1 - (k - 1) (q - 1) x^k) - (x^{k + 1} (q - 1) (k q^k x^{k - 1} (1 - q x) + q (1 - (q x)^k)))/(1 - q x)^2]$

Attempt to reformat:

$${1\over1-k(q-1)x^k}B$$ where $$B={(1-(qx)^k)(1-(k-1)(q-1)x^k)\over(1-qx)}-{x^{k+1}(q-1)(kq^kx^{k-1}(1-qx)+q(1-(qx)^k))\over(1-qx)^2}$$

Edit: I found a textbook online that claims the generating function is this:

$(1-x^k)/(1-qx+(q-1)x^{k+1})$

But seeing as I didn't get anything close to that and they provide little proof in the text, I am not sure it is correct either.

Answer 1

Suppose you do have $$a_{n+k}=(q-1)\sum_{i=n}^{n+k-1}a_i$$ for all $n$. Then $$a_{n+k+1}=(q-1)\sum_{i=n+1}^{n+k}a_i$$ and so $$a_{n+k+1}-a_{n+k}=(q-1)(a_{n+k}-a_n).$$ We get the alternative recurrence $$a_{n+k+1}=qa_{n+k}-(q-1)a_n.$$ Also $$a_k=(q-1)\sum_{i=0}^{k-1}q^{i}=q^k-1.$$

Let $$A(x)=\sum_{n=0}^\infty a_nx^n$$ be the generating function. Then \begin{align} (1-qx+(q-1)x^{k+1})A(x)&=\sum_{n=0}^\infty a_nx^n -q\sum_{n=0}^\infty a_n x^{n+1}+(q-1)\sum_{n=0}^\infty a_nx^{n+k+1}\\ &=\sum_{n=0}^k a_nx^n-q\sum_{n=0}^{k-1}a_n x^{n+1} +\sum_{n=0}^\infty(a_{n+k+1}-qa_{n+k}+(q-1)a_n)x^{n+k-1}\\ &=\sum_{n=0}^{k-1}q^nx^n+(q^k-1)x^k-q\sum_{n=0}^{k-1}q^nx^{n+1}+0\\ &=1-x^k \end{align} etc.

Answer 2

Let's say $f(x)$ is the generating function for a string of characters from $\{0,1,2,\dots,q-1\}$ with no substring of $k$ or more consecutive $0$s.

An acceptable string is

• a string of zero to $k-1$ $0$s

followed by

• an empty string,
• or a non-$0$ character (with $q-1$ choices), followed by an acceptable string.

Stated in the form of an equation, $$\begin{align} f(x) &= (1+x+x^2 + \dots +x^{k-1})\; (1+(q-1)x f(x)) \\ &= \frac{1-x^k}{1-x} \; (1+(q-1)x f(x)) \end{align}$$

Solving for $f(x)$, we have $$f(x) = \frac{1-x^k}{1-qx+(q-1)x^{k+1}}$$