The following is an assignment question I have been trying to work out for quite some time.
Let $C(x,y)=\sum_{n,k \geq 0} c_{n,k} x^{n} y^{k}$, where $c_{n,k}$ is the number of binary strings of length $n$ with $k$ blocks. Prove that \begin{equation} C(x,y)=\frac{1-x+yx}{1-x-yx} \end{equation} Then show that $[x^{n}] \frac{\delta}{\delta y} C(x,y) \left|_{y=1} \right.$ is the total number of blocks among all binary strings of length $n$.
I know that the first step is to find a recurrence relation for $c_{n,k}$. Consider a arbitrary binary string of length $n$ with $k$ blocks. The first digit is either zero or one; the difference is immaterial. The second digit is either the same or the opposite of the first digit.
In the first case, when the second digit is the same as the first, there are $k$ blocks in the $(n-1)$ digit long substring. The number of such substrings is $c_{n-1,k}$. In the second case, when the second digit is different than the first, one block has been found and so $(k-1)$ blocks remain in the $(n-1)$ digit long substring. The number of such substrings is $c_{n-1,k-1}$. This gives the following recurrence relation: \begin{equation} c_{n,k}=c_{n-1,k}+c_{n-1,k-1}. \end{equation}
If $k>n$, then $c_{n,k}=0$ because there is no way to have more blocks of digits than digits in a binary string. If $k=n$, then $c_{n,k}=2$ because there are two binary strings with alternating digits.
Let $C(x,y)= \displaystyle\sum_{n=0}^{\infty} \sum_{k=0}^{\infty} c_{n,k} x^{n}y^{k}$. Find the bivariate generating function. \begin{equation} \begin{aligned} \sum_{k=1}^{\infty} c_{n,k} y^{k} &= \sum_{k=1}^{\infty} c_{n-1,k} y^{k} + \sum_{k=1}^{\infty} c_{n-1,k-1} y^{k} \\ \sum_{n=1}^{\infty} \sum_{k=1}^{\infty} c_{n,k} x^{n}y^{k} &= \sum_{n=1}^{\infty} \sum_{k=1}^{\infty} c_{n-1,k} x^{n}y^{k} + \sum_{n=1}^{\infty} \sum_{k=1}^{\infty} c_{n-1,k-1} x^{n}y^{k} \\ \sum_{n=1}^{\infty} \sum_{k=1}^{\infty} c_{n,k} x^{n}y^{k} &= x\sum_{n=1}^{\infty} \sum_{k=1}^{\infty} c_{n-1,k} x^{n-1}y^{k} + xy\sum_{n=1}^{\infty} \sum_{k=1}^{\infty} c_{n-1,k-1} x^{n-1}y^{k-1} \\ \end{aligned} \end{equation} \begin{equation} \begin{aligned} \sum_{n=0}^{\infty} \sum_{k=1}^{\infty} c_{n,k} x^{n}y^{k} - \sum_{k=1}^{\infty} c_{0,k}x^{0}y^{k} &= x\sum_{n=0}^{\infty} \sum_{k=1}^{\infty} c_{n,k} x^{n}y^{k} + xy\sum_{n=0}^{\infty} \sum_{k=1}^{\infty} c_{n,k-1} x^{n}y^{k-1} \\ \sum_{n=0}^{\infty} \sum_{k=0}^{\infty} c_{n,k} x^{n}y^{k} - \sum_{n=0}^{\infty} c_{n,0} x^{n} &= x \left( \sum_{n=0}^{\infty} \sum_{k=0}^{\infty} c_{n,k} x^{n}y^{k} - \sum_{n=0}^{\infty} c_{n,0} x^{n} \right) + xy\sum_{n=0}^{\infty} \sum_{k=0}^{\infty} c_{n,k} x^{n}y^{k} \\ \sum_{n=0}^{\infty} \sum_{k=0}^{\infty} c_{n,k} x^{n}y^{k} - 2 &= x \sum_{n=0}^{\infty} \sum_{k=0}^{\infty} c_{n,k} x^{n}y^{k} - 2x + xy\sum_{n=0}^{\infty} \sum_{k=0}^{\infty} c_{n,k} x^{n}y^{k} \\ C(x,y)-1&= xC(x,y)-x+xyC(x,y) \\ (1-x-xy)C(x,y) &= 2-2x \\ C(x,y) &= \frac{2-2x}{1-x-xy} \end{aligned} \end{equation}
At this point, I am unsure how to proceed. Furthermore, I know that I have clearly made an error above but I cannot seem to find it.
Any help would be appreciated!
The recurrence can be written
$$c_{n,k}=c_{n-1,k}+c_{n-1,k-1}+[n=k=0]-[n=1][k=0]+[n=k=1]\;,$$
where the square brackets are Iverson brackets; this makes the recurrence valid for all $n,k\ge 0$ on the assumption that $c_{n,k}=0$ if either $n$ or $k$ is negative. This is an easy way to build the initial conditions into the recurrence, and although I’ve not waded through the details, it looks as if this is probably where you went a little bit astray.
Multiply the recurrence through by $x^ny^k$ and sum over $n,k\ge 0$:
$$\begin{align*} C(x,y)&=\sum_{n,k\ge 0}c_{n,k}x^ny^k\\\\ &=\sum_{n,k\ge 0}c_{n-1,k}x^ny^k+\sum_{n,k\ge 0}c_{n-1,k-1}x^ny^k+1-x+xy\\\\ &=xC(x,y)+xyC(x,y)+1-x+xy\;, \end{align*}$$
so
$$C(x,y)=\frac{1-x+xy}{1-x-xy}\;.$$