Number of bit strings of length $n$ with no $k_1+1$ consecutive 0s and no $k_2+1$ consecutive 1s. Just as the question asks. I am trying to calculate the number of bit strings of length $n$ with a maximum of $k_1$ consecutive $0s$ and $k_2$ consecutive 1s. Of course we assume $k_1+k_2\leq n$. I am trying to set up a recurrence but I am completely puzzled. I know that to not get two consecutive 0s, we have the recurrence $a_n=a_{n-1}+a_{n-2}$ with $a_1=2$ and $a_2=3$. However I can't seem to generalize this to no more than $k_1$ $0s$ especially that you have the second condition of no more than $k_2$ 1s.
 A: Any string fulfilling the wanted constraints has one of the following structures:
$$ 0^{a_1}1^{b_1}0^{a_2}1^{b_2}\ldots \qquad 1^{b_1}0^{a_1}1^{b_2}0^{a_2}\ldots $$
with $a_i\leq k_1, b_j\leq k_2$ and $\sum a_i+\sum b_j = n$. Assume that we want to compute how many strings are there of the $0^{a_1}1^{b_1}0^{a_2}1^{b_2}0^{a_3}$ kind. They are given by the coefficient of $x^n$ in the product
$$ \left(1+x+x^2+\ldots+x^{k_1}\right)^3\cdot\left(1+x+x^2+\ldots+x^{k_2}\right)^2 = p_{k_1}(x)^3 p_{k_2}(x)^2$$
hence by accounting for all possible kinds, the answer is given by the coefficient of $x^n$ in
$$ \sum_{r\geq 0}\left(p_{k_1}(x)^r p_{k_2}(x)^{r+1}+p_{k_1}(x)^{r+1}p_{k_2}(x)^r\right) =\color{red}{\frac{p_{k_1}(x)+p_{k_2}(x)}{1-p_{k_1}(x)\,p_{k_2}(x)}}.$$
A: Here is a comment showing how to compute the generating functions from
first  principles.  We   may  then  continue  as  in   the  answer  by
@MarkusScheuer.
Using $z$ for zero and $w$ for one we have the generating function
$$(1+z+z^2+\cdots+z^{k_1})
\sum_{q\ge 0} (w+w^2+\cdots+w^{k_2})^q (z+z^2+\cdots+z^{k_1})^q
\\ \times (1+w+w^2+\cdots+w^{k_2}).$$
As we are only interested in the count we may write this as
$$(1+z+z^2+\cdots+z^{k_1})
\sum_{q\ge 0} (z+z^2+\cdots+z^{k_2})^q (z+z^2+\cdots+z^{k_1})^q
\\ \times (1+z+z^2+\cdots+z^{k_2}).$$
This is
$$\frac{1-z^{k_1+1}}{1-z}
\left(\sum_{q\ge 0} z^q \frac{(1-z^{k_2})^q}{(1-z)^q}
z^q \frac{(1-z^{k_1})^q}{(1-z)^q}\right)
\frac{1-z^{k_2+1}}{1-z}
\\ = \frac{1-z^{k_1+1}}{1-z} \frac{1-z^{k_2+1}}{1-z}
\frac{1}{1-z^2(1-z^{k_1})(1-z^{k_2})/(1-z)/(1-z)}
\\ = \frac{(1-z^{k_1+1})(1-z^{k_2+1})}
{1-2z+z^2-z^2(1-z^{k_1})(1-z^{k_2})}
\\ = \frac{1-z^{k_1+1}-z^{k_2+1}+z^{k_1+k_2+2}}
{1-2z+z^{k_1+2}+z^{k_2+2}-z^{2+k_1+k_2}}.$$
Some Maple code to verify these follows.

RL :=
proc(n, k1, k2)
    option remember;
    local ind, d, pos, cur, run, runs, res,
    zmax, wmax;

    res := 0;

    for ind from 2^n to 2*2^n-1 do
        d := convert(ind, base, 2);

        cur := -1; pos := 1;
        run := []; runs := [];


        while pos <= n do
            if d[pos] <> cur then
                if nops(run) > 0 then
                    runs :=
                    [op(runs), [run[1], nops(run)]];
                fi;

                cur := d[pos];
                run := [cur];
            else
                run := [op(run), cur];
            fi;

            pos := pos + 1;
        od;

        runs := [op(runs), [run[1], nops(run)]];

        zmax := max(seq(`if`(r[1] = 0, r[2], 0), r in runs));
        wmax := max(seq(`if`(r[1] = 1, r[2], 0), r in runs));

        if zmax <= k1 and wmax <= k2 then
            res := res + 1;
        fi;
    od;

    res;
end;

X :=
proc(n, k1, k2)
option remember;
local gf;

    gf :=
    (1-z^(k1+1)-z^(k2+1)+z^(k1+k2+2))
    /(1-2*z+z^(k1+2)+z^(k2+2)-z^(k1+k2+2));

    coeftayl(gf, z=0, n);
end;

A: You can set up a set of coupled recurrences.  Let $A(k,n)$ be the number of acceptable $n$ bit strings that end with $k\ 0$'s and $B(k,n)$ be the number of acceptable $n$ bit strings ending with $k\ 1$'s.  Then $A(k+1,n+1)=A(k,n)$ and $A(1,n+1)=\sum_{i=0}^{k_2}B(i,n)$ and similarly for $B(k,n+1)$  Put the $A$'s and $B$'s into a column vector and you have a matrix that you multiply by the vector to increase the length of the string.  You can diagonalize the matrix and find eigenvalues to find the asymptotic rate of growth.
A: Let me to begin with changing the $k$s to $k_0$ and $k_1$, so to help and remember their association with the values.  
First step is to fix the total number of ones  at , let say $0 \leqslant q \leqslant n$ (and the number of zeros is consequently fixed).
We know the total number of ways to obtain strings of length $n$ with $q$ ones, so we will at end accomodate for that. 
Then your scheme is equivalent to many other combinatorial ones, e.g. 
number of lattice paths from $(0,0)$ to $(n-q,q)$ with steps from $\left\{ {\left( {1 \ldots k_0 ,0} \right),\left( {0,1 \ldots k_1 } \right)} \right\}$.
After fixing the total number of $1$s, let now fix the number of $1$-blocks at $m$.
The number of $0$-blocks will be either $m$ (if the string starts and ends with different values), or $m-1$ (starts and ends with $1$) or $m+1$ (starts and ends with $0$).
The number of ways to arrange $q$ ones into $m$ blocks with no more than $k_1$ in each, is the number of compositions of $q$ in $m$ parts of max size $k_1$.
An expression for that can be derived from the answers to Rolling dice problem (re. to there for details), where we have:
$$
N_{\,b} (s,r,m) = \text{No}\text{. of solutions to}\;\left\{ \begin{gathered}
  0 \leqslant \text{integer  }x_{\,j}  \leqslant r \hfill \\
  x_{\,1}  + x_{\,2}  +  \cdots  + x_{\,m}  = s \hfill \\ 
\end{gathered}  \right.
$$
which can be expressed as
$$
N_{\,b} (s,r,m)\quad \left| {\;0 \le {\rm integers}\;s,r,m} \right.\quad  = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,{s \over r}\, \le \,m} \right)} {\left( { - 1} \right)^{\,k} \left( \matrix{
  m \cr 
  k \cr}  \right)\left( \matrix{
  s + m - 1 - k\left( {r + 1} \right) \cr 
  s - k\left( {r + 1} \right) \cr}  \right)}
$$
In our case, since the number of $1$s goes from $1$ to $k_1$, we shall replace $r$ with $k_1-1$ and $s$ with $q-m$.
Now we shall intersperse the $1$-blocks into the $0$-blocks "comb-to-comb". 
The number of ways to make up the $0$-blocks follows the same formula, with the appropriate parameters.
Considering that the "starting-block($0$/$1$)-end-block($0$/$1$)" represents a partition of the considered strings,
it is not difficult to make up the four parts and conclude:
$$
\begin{gathered}
  N(k_{\,0} ,k_{\,1} ,n,q,m) =  \hfill \\
   = N_b (q - m,k_{\,1}  - 1,m)\left( {N_b (n - q - m + 1,k_{\,0}  - 1,m - 1) + 2N_b (n - q - m,k_{\,0}  - 1,m) + N_b (n - q - m - 1,k_{\,0}  - 1,m + 1)} \right) \hfill \\ 
\end{gathered} 
$$
In summing through $m$ and then $p$ (after multiplying by C(n,q)), note that in the $N_{\,b} (s,r,m)$ formula, the bounds in the summation and in the parameters may be omitted (practically: stretched  from $0$ to a suitable max), 
because the binomials (as defined and as written), or the sum itself, are null for $m<k$ and $mr<s$, etc., being enough to ensure that $0 \leqslant r$.
