Generating function for number of words with no k consecutive 0's? 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.
 A: 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.
A: 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}}$$
