How many bit strings of length $n$ contain exactly $k$ blocks of "$10$"? How many bit strings of length $n$ contain exactly $k$ blocks of "$10$"?
My attempt: Let $F(n, k)$ be the number of bit strings of length $n$ that contain exactly $k$ blocks of $10.$ Note that for $k \neq0, $ $F(0, k) = F(1, k)= 0.$
Consider a bit string of length $n$ where $ n \geq 2.$
Every bit string either begins with:
1) $10$,
or
2) $01$, $00$ or $11.$ 
In the former case, we get $F(n-2, k-1)$ since the remaining $n-2$ bits must contain $k-1$ blocks of $10$ in exactly $F(n-2, k-1)$ ways.
In the latter case, in either of the $3$ situations we get $F(n-2, k)$ since the remaining $n-2$ bits must contains $k$ blocks of $10$ in $F(n-2, k)$ ways.
Therefore for $n \geq 2, k \geq 1$ we have:
$F(n, k) = F(n-2, k-1)+ 3F(n-2, k)$.
For $k \geq 1$ let $A_k(x) = \displaystyle \sum_{n \geq2}F(n,k)x^n$ (and let $A_0(x)=1$) then multiplying the above recurrence by $x^n$ and summing over all $n \geq 2$ we get:
$A_k(x) = x^2 A_{k-1}(x) +3x^2A_{k}(x) $
$\Rightarrow A_k(x) = \dfrac{x^2}{1-3x^2} A_{k-1}(x)$
$\Rightarrow A_{k}(x) = \dfrac{x^{2k}}{(1-3x^2)^k} $
$\Rightarrow F(n, k) = [x^n] A_k(x)$
$\Rightarrow F(n, k) = [x^n] \dfrac{x^{2k}}{(1-3x^2)^k}$
$\Rightarrow F(n, k) = [x^{n-2k}] \displaystyle \sum_{r \geq 0} \binom{k+r-1}{r} 3^r x^{2r}$
which clearly gives a wrong answer for odd $n$. Could somebody point out where in the above calculation have I gone wrong? Thanks in advance.
 A: Essentially this amounts to finding the places where the string switches from a run of $1$'s to a run of $0$'s. Note that there are $n-1$ places where such a switch may occur (between each pair of numbers). In any event, there must be $k$ places where the string switches from $1$ to $0$:


*

*If the string starts and ends with $0$, then (since it starts with $0$) there must also be $k$ places where it switches from $0$ to $1$. There are $\binom{n-1}{2k}$ ways of making these choices.

*If the string starts with $1$ and ends with $0$, then there must (since it ends in $0$) also be $k-1$ places where it switches from $0$ to $1$; there are $\binom{n-1}{2k-1}$ ways of making these choices.

*If the string starts with $0$ and ends with $1$, then there must (since it starts with $0$) also be $k+1$ places where it switches from $0$ to $1$; there are $\binom{n-1}{2k+1}$ ways of making these choices.

*Finally, if the string starts and ends with $1$, there must (since it ends with $1$) also be $k$ places where it switches from $0$ to $1$. There are $\binom{n-1}{2k}$ ways of making these choices.
So finally, the total number of such strings is
$$\binom{n-1}{2k} + \binom{n-1}{2k-1} + \binom{n-1}{2k+1} + \binom{n-1}{2k}
   = \binom{n}{2k} + \binom{n}{2k+1} = \binom{n+1}{2k+1}.$$
A: Thanks for the insight. I used a similar technique for a similar problem. I wrote this up for my assignment which is due in a week. Although I believe that I found the recurrence relation correctly, I am unable to go about extracting the coefficients from a quadratic raised to a negative k-th power. Could you please be able to help me how to proceed?
Let $f(n, k)$ represent the number of strings made of $\{a, b\}$ where $k$ is the number of occurrences of ''$ab$'' in a string of length $n$. Note that the string can begin with $ab, aa, bb$, or $ba$. If it begins with $ab$, then there are exactly $f(n-2, k-1)$ number of strings remaining. If it begins with $bb$, then there are exactly $f(n-2, k)$ strings remaining. If it begins with $aa$, or $ba$, then there are exactly $f(n-1, k)$ strings remaining. Thus we have the recurrence relation $f(n, k) = f(n-2, k-1) + f(n-2, k) + 2f(n-1, k)$. Trivially enough, we have that $f(0, k) = f(1, k) = 0$ for any non-zero $k$. Define $A_{k}(x) = \displaystyle \sum_{n=2}^{\infty} f(n, k)x^{n}$. Note that $A_{0}(x) = \displaystyle \sum_{n\geq 2} f(n, 0)x^{n} = \displaystyle \sum_{n \geq 2} (n+1)x^{n}.$
 Thus $A_{k}(x) = \sum_{n=2}^{\infty} \Big[ f(n-2, k-1)x^{n} + f(n-2, k)x^{n} + 2f(n-1, k)x^{n}\Big].$
It follows that $A_{k}(x) = \displaystyle \sum_{n=2}^{\infty} x^{2} f(n, k-1)x^{n} + x^{2} f(n, k)x^{n} + 2x f(n, k)x^{n}$
Thus, \begin{align*}
A_{k}(x) = x^{2} A_{k-1}(x) + x^{2} A_{k}(x) + 2x A_{k}(x)\\
\implies A_{k}(x) = \displaystyle \frac{x^{2}}{1+2x-x^{2}}A_{k-1}(x)\\
\implies A_{k}(x) = \displaystyle \frac{x^{2}}{1+2x-x^{2}} \cdot \Big( \displaystyle \frac{x^{2}}{1+2x-x^{2}} A_{k-2}(x) \Big) \\
\therefore A_{k}(x) = \displaystyle \Bigg(\frac{x^{2}}{1+2x-x^{2}}\Bigg)^{k} \displaystyle (n+1) \sum_{n \geq 2} x^{n}\\
\therefore A_{k}(x) = (n+1) \displaystyle \frac{x^{2k+2}}{(1+2x-x^{2})^{k} (1-x)}\\
\end{align*}
But $f(n, k) = [x^{k}] A_{k}(x)$
\begin{align*}
\therefore f(n, k) = [x^{n-2-2k}] \displaystyle (n+1) \frac{1}{(1+2x-x^{2})^{k} (1-x)}\\
\therefore f(n, k) = [x^{n-2k-2}] (n+1) \displaystyle (1+2x-x^{2})^{-k} (1-x)^{-1}\\
\end{align*}
This is the part where I'm stuck at. Please help.
