I am trying to find the generating function of a sequence in the language of bitstrings, $X$, where each bitstring contains no more than 3 consecutive zeros.
I have come up with the recurrence relation for a sequence $h_n$ of length $n$ as follows: (I am not 100% sure that it is correct, either)
$h_n=h_{n-1}+h_{n-2}+h_{n-3} + h_{n-4}$
How do I derive a generating function using this?
A recursion like this leads to a function equation: define $H(x) = \sum_n h_nx^n$. Then $H(x) = h_0 + h_1x h_2x^2 + h_3x^3 + \sum_{n \ge 4} h_nx^n$.
The last part can be replaced using the recursion:
$$\sum_{n \ge 4} (h_{n-1} + h_{n-2} + h_{n-3} + h_{n-4})x^n = x\sum_{n \ge 4} h_{n-1} x^{n-1} + x^2 \sum_{n \ge 4} h_{n-2}x^{n-2} + x^3 \sum_{n \ge 4} h_{n-3}x^{n-3} +\\ x^4 \sum_{n \ge 4} h_{n-4}x^{n-4}$$
Now note that $\sum_{n \ge 4} h_{n-4}x^{n-4} = \sum_n h_n x^n = H(x)$ again, while $\sum_{n \ge 4} h_{n-3}x^{n-3} = H(x) - h_0$ etc.
Working it all out gives an equation into $H(x)$ that you can hopefully solve...