Производящие функции

[RIP]

Навеяно этим делом.
Фиксируем некоторую последовательность длины $l$ из нулей и единиц $a\in\{0;1\}^l$. Для каждого $n\in\mathbb{N}_0$ обозначим через $N_a(n)$ количество строк из нулей и единиц длины $n$ (под строкой длины $0$ подразумевается пустая строка), которые не содержат $a$ в качестве подстроки. Рассмотрим производящую функцию

$$f_a(z)=\sum_{n=0}^\infty N_a(n)z^n.$$

Докажите или опровергните:
Для любой последовательности $a$ $f_a(z)$ является рациональной функцией вида

$$f_a(z)=\frac{P_a(z)}{Q_a(z)},\quad P_a(z)=1+\alpha_1 z+\ldots+\alpha_{l-1}z^{l-1}\in\mathbb{Z}[z],\ Q_a(z)=1+\beta_1 z+\ldots+\beta_l z^l\in\mathbb{Z}[z],\ \beta_l=\pm1,\ (P_a(z),Q_a(z))=1.$$

Например,

$$f_{00\ldots0}(z)=\frac{1+z+\ldots+z^{l-1}}{1-z-z^2-\ldots-z^l};$$

$$f_{0\ldots01\ldots1}(z)=\frac1{(1-z)(1-z-z^2-\ldots-z^{l-1})};$$

$$f_{0\ldots01\ldots10}(z)=\frac{1+z^{l-1}}{(1-z)(1-z-\ldots-z^{l-2})-z^l}.$$

P.S. Просьба ссылки на готовые решения выкладывать.

[maxal]

Ну если на готовые можно, то вот например пункты 5.2 и 5.3

[RIP]

О, пасиба. А я думал, что задача совсем простая, поскольку те 3 случая, что я привёл, получаются в пару строчек. Теперь понятно, что не совсем простая...