Estimate asymptotic behaviour by looking on ordinary generating function I am interested on the asymptotic behaviour ($m \rightarrow \infty$) of the number of $q$-ary strings of length $m$, which do not contain $k$ consecutive zeros.
The link Number of q-ary strings of length m which do not contain k consecutive zeros gives some derivations for that number.
In particular, the ordinary generating function of this number is
$$ F(z) = \frac{1-z^k}{1-qz+(q-1)z^{k+1}} $$
where $q$ is the size of the alphabet $\{ 0,1,...,q-1 \}$.
Now I hope, there is some simpler expression $g(q,m,k)$ for the asymptotic behaviour of this number, i.e. $f_m \sim g(q,m,k)$ for $m \rightarrow \infty$. We state $k<m$ and assume that $k$ is very small relatively to $m$.
Can someone help me with my problem?
 A: Fixing $q$ and $k$ we ask about the asymptotics of $[z^m] F(z)$ where
$$F(z) = \frac{1-z^k}{1-qz+(q-1)z^{k+1}}.$$
We will  suppose that $m\ge  k$ since  the answer is  $q^m$ otherwise.
First verify that the poles $\rho$  are all simple. We get with $\rho$
a root of the denominator
$$\lim_{z\to\rho} \frac{z-\rho}{1-qz+(q-1)z^{k+1}}
= \lim_{z\to\rho} \frac{1}{-q + (q-1)(k+1)z^{k}}.$$
Now we have
$$-q + (q-1)(k+1)\rho^{k} = -q + (q-1)(k+1)\rho^{k+1}/\rho
\\ = -q + (k+1)(q\rho-1)/\rho.$$
If this were zero we would get
$$\rho = \frac{k+1}{kq}.$$
which  is  rational.   Applying  the  rational  root  theorem  to  the
denominator of $F(z)$ we must have
$$\frac{k+1}{kq} = \frac{1}{r}$$
where $r|(q-1).$ This requires  $q=p(k+1)$ where $kp|(q-1).$ There are
two cases.  The first is  $kp=q-1$ which implies $q=q-1+p$ i.e. $p=1.$
We get  $\rho = 1/k$  however for  $1-(k+1)/k + k  / k^{k+1} =  0,$ we
would need  $1/k^k = 1/k$ so  no contribution from this  case (here we
have assumed  that $k\ge  2$ since the  answer is  $(q-1)^m$ trivially
otherwise). Second  case is  that $kp$  is a  proper divisor  of $q-1$
which  gives the  bound  $q\le (q-1)/2  +  (q-1)/4$, a  contradiction.
Hence all poles are simple. 
Working with
$$G(z) = \frac{1}{1-qz+(q-1)z^{k+1}}.$$
we have under these conditions
$$G(z) = \sum_\rho \frac{1}{z-\rho} \mathrm{Res}_{z=\rho} G(z)
= - \sum_\rho \frac{1}{\rho} \frac{1}{1-z/\rho} 
\mathrm{Res}_{z=\rho} G(z).$$
This last  expression tells us  that we need  the pole closest  to the
origin for  the asymptotics.   Observe that with  $|z|\lt 1$  the term
$1-qz+(q-1)z^{k+1}$ is dominated  by $1-qz$ and hence there  must be a
pole in  the vicinity of  $z=1/q$, which  it will require  numerics to
approximate (e.g.  start  Newton's method at $1/q$) and  which we will
call $\beta.$ The complex  poles come in pairs so if  we can show that
it is real  and that there are  no others with $|z|<1/q$  we have that
the contribution from $\beta$ yields  the asymptotics. At this time we
will  show  that  there  is  one  zero  from  the  denominator  inside
$|z|=(1/q)\times q/(q-1) = 1/(q-1)$  by Rouche's Theorem, taking $f(z)
= 1-qz+(q-1)z^{k+1}$ and $g(z) = - qz$ where
$$|f(z)-g(z)| = 
|1+(q-1)z^{k+1}| \le 1 + \frac{1}{(q-1)^k}
\quad\text{and}\quad |g(z)| = \frac{q}{q-1}
= 1 + \frac{1}{q-1}.$$
The conditions for the theorem  hold (i.e. $|f(z)-g(z)| \lt |g(z)|$ on
$|z|=1/(q-1)$) when $k\ge  2$ which we assumed so $f(z)$  has the same
number of zeros  inside the contour as $g(z)$ and  $g(z)$ has just one
root there, so  $f(z)$ does as well  and this is our  pole $\beta.$ As
there is just one it must be real.
To conclude here it remains to extract coefficients which yields
$$-\frac{1}{\beta} 
\left(\frac{1}{\beta^m}-\frac{1}{\beta^{m-k}}\right)
\times \frac{1}{-q+(k+1)(q\beta-1)/\beta}.$$
We factorize to obtain the constant and find
$$\bbox[5px,border:2px solid #00A000]{
\frac{1}{(k+1)(q\beta-1)-q\beta}
\left(\beta^k-1\right)
\times \frac{1}{\beta^{m}}.}$$
This formula was  verified numerically where $\beta$  was computed and
the evidence indicates rapid convergence with $m.$ 
Addendum.  To  help OP  we  also  include  the closed  form  which
requires
$$[z^m] \frac{1}{1-qz+(q-1)z^{k+1}}
= [z^m] \sum_{p\ge 0} z^p (q-(q-1) z^k)^p
\\ = \sum_{p=0}^m [z^{m-p}] (q-(q-1) z^k)^p
= \sum_{p=0}^m [z^p] (q-(q-1) z^k)^{m-p}
\\ = \sum_{p=0}^{\lfloor m/k\rfloor} [z^{kp}] (q-(q-1) z^k)^{m-kp}.$$
Here we must have $m-kp\ge p$ and we find
$$[z^m] G(z) = g_m = \sum_{p=0}^{\lfloor m/(k+1)\rfloor} 
{m-kp\choose p} (1-q)^p q^{m-(k+1)p}$$
and the closed form is given by $f_m = [z^m] F(z) = g_m-g_{m-k}.$ 
