# How to get closed form from generating function?

I have this generating function:

$$\frac{1}{2}\, \left( {\frac {1}{\sqrt {1-4\,z}}}-1 \right) \left( \,{ \frac {1-\sqrt {1-4\,z}}{2z}}-1 \right)$$

and I know that $\frac {1}{\sqrt {1-4\,z}}$ is the generating function for the sequence $\binom {2n} {n}$, and $\frac {1-\sqrt {1-4\,z}}{2z}$ is the generating function for the sequence $\frac {1}{n+1}\binom{2n} {n}$.

Now, I thought that I could substitute those in there, and where they multiply I'll use a summation like this:

$$\frac{1}{2}\left( 1-\frac{1}{n+1}\binom{2n} {n}-\binom{2n} {n} + \sum_{k=0}^n \frac{1}{k+1} \binom{2k}{k}\binom{2(n-k)}{n-k} \right)$$

Could this be right? It doesn't seem to work when I try in Maple. What else could I do?

I already know that the end sequence will be $\binom{2n-1}{n-2}$ if this can help...

-
Be careful with your terminology: everywhere that you’ve written series, you should have sequence. – Brian M. Scott Dec 2 '11 at 18:08
yep..I fixed it! – Adam Smith Dec 2 '11 at 18:11
Note that $1$ (the constant function) is not the generating function for $1$ (the constant sequence), but rather for $\delta_{n}$ (the sequence with $a_0=1$ and $a_{n>0}=0$). – mjqxxxx Dec 2 '11 at 18:25
uh.. that's right. So what should I put there? some function of n that gives 1 on n=0 and 0 the rest of the time? What function is that? – Adam Smith Dec 2 '11 at 19:03
@Adam: I like the Iverson bracket for that purpose. – Brian M. Scott Dec 5 '11 at 21:27

Expanding the product, and after some algebra: $$g(z) = \frac{1}{2} \left(\frac{\sqrt{1-4 z}-1}{z}+\frac{1}{\sqrt{1-4 z}}+1\right)$$ Using generalized binomial theorem: $$[z]^n g(z) = \frac{1}{2} \left( \delta_{n,0} + \binom{1/2}{n+1} (-4)^{n+1} + \binom{-1/2}{n} (-4)^n \right)$$ Using $$\begin{eqnarray} \binom{-1/2}{n} - 4 \binom{1/2}{n+1} &=& \frac{\Gamma(1/2)}{n! \Gamma(1/2-n)} - \frac{\Gamma(3/2)}{(n+1)! \Gamma(1/2-n)} \\ &=& (-1)^n (n-1) \frac{\Gamma(1/2+n) \Gamma(n+1)}{\Gamma(1/2) (n+1)!n!} \\ &=& (-1)^n (n-1) \frac{(2n)!}{4^n (n+1)!n!} \\ &=& (-1)^n \frac{(2n-1)!}{2 \cdot 4^{n-1} (n+1)!(n-2)!} = 2 \cdot \frac{(-1)^n}{4^n} \cdot \binom{2n-1}{n+1} \end{eqnarray}$$ Hence, using Iverson's bracket: $$[z]^n g(z) = \binom{2n-1}{n+1} \left[ n \ge 2 \right]$$

-

It’s not necessary to use the generalized binomial theorem and the gamma function. Let $$g(x)=\frac12\left(\frac1{\sqrt{1-4x}}-1\right) \left(\frac{1-\sqrt{1-4x}}{2x}-1\right)$$ and $u=\sqrt{1-4x}$. Then

\begin{align*} g(x)&= \frac12\left(\frac1u-1\right)\left(\frac{1-u}{2x}-1\right)\\ &=\frac12\left(\frac{1-u}{2xu}-\frac{1-u}{2x}-\frac1u+1\right)\\ &=\frac12\left(\frac1{2xu}-\frac1x+\frac{u}{2x}-\frac1u+1\right)\\ &=\frac12\left(\frac{1+u^2}{2xu}-\frac1x-\frac1u+1\right)\\ &=\frac12\left(\frac{1-2x}{xu}-\frac1x-\frac1u+1\right)\\ &=\frac12\left(\frac1{xu}-\frac1x-\frac3u+1\right)\\ &=\frac12\left(\frac1x\left(\frac1u-1\right)+1-\frac3u\right)\\ &=\frac12\left(\sum_{k\ge 1}\binom{2k}k x^{k-1}+1-3\sum_{k\ge 0}\binom{2k}k x^k\right)\\ &=\frac12\left(1+\sum_{k\ge 0}\left(\binom{2k+2}{k+1}-3\binom{2k}k\right)x^k\right)\\ &=\frac12\sum_{k\ge 2}\left(\binom{2k+2}{k+1}-3\binom{2k}k\right)x^k. \end{align*}

Now

\begin{align*} \binom{2k+2}{k+1}-3\binom{2k}k&=\binom{2k+1}k+\binom{2k+1}{k+1}-3\binom{2k}k\\ &=\binom{2k+1}k+\binom{2k}k+\binom{2k}{k-1}-3\binom{2k}k\\ &=\binom{2k+1}k+\binom{2k}{k+1}-2\binom{2k}k\\ &=\binom{2k}{k-1}+\binom{2k}k+\binom{2k}{k+1}-2\binom{2k}k\\ &=\binom{2k}{k-1}-\binom{2k}k+\binom{2k}{k+1}\\ &=\binom{2k}{k-1}-\binom{2k}k+\binom{2k-1}k+\binom{2k-1}{k+1}\\ &=\binom{2k}{k-1}-\binom{2k-1}{k-1}-\binom{2k-1}k+\binom{2k-1}k+\binom{2k-1}{k+1}\\ &=\binom{2k}{k-1}-\binom{2k-1}{k-1}+\binom{2k-1}{k+1}\\ &=\binom{2k-1}{k-2}+\binom{2k-1}{k+1}\\ &=2\binom{2k-1}{k-2}, \end{align*}

so $\displaystyle[x^k]g(x)=\binom{2k-1}{k-2}$, as desired.

-

Expand out the product, and look at what each term is the generating function for.

-

With this type of problem Lagrange inversion is the preferred approach. Suppose we seek to extract coefficients from $$Q(z) = \frac{1}{2} \left(\frac{1}{\sqrt{1-4z}}-1\right) \left(\frac{1-\sqrt{1-4z}}{2z}-1\right).$$

The closed form for the coefficients is $$[z^n] Q(z) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{2} \left(\frac{1}{\sqrt{1-4z}}-1\right) \left(\frac{1-\sqrt{1-4z}}{2z}-1\right) \; dz.$$

Now put $1-4z=w^2$ so that $1/4-z=1/4 \times w^2$ or $z=1/4\times(1-w^2)$ and $dz = -1/2 \times w\; dw.$ This gives for the integral $$-\frac{1}{2\pi i} \int_{|w-1|=\epsilon} \frac{w}{4} \frac{4^{n+1}}{(1-w^2)^{n+1}} \left(\frac{1}{w}-1\right) \left(\frac{1-w}{2\times 1/4\times(1-w^2)}-1\right) \; dw \\ = -\frac{1}{2\pi i} \int_{|w-1|=\epsilon} \frac{4^n}{(1-w^2)^{n+1}} (1-w) \left(\frac{2}{1+w}-1\right) \; dw \\ = -\frac{1}{2\pi i} \int_{|w-1|=\epsilon} \frac{4^n}{(1-w)^n (1+w)^{n+1}} \left(\frac{2}{1+w}-1\right) \; dw \\ = -\frac{1}{2\pi i} \int_{|w-1|=\epsilon} \frac{4^n}{(1-w)^n (1+w)^{n+1}} \frac{1-w}{1+w} \; dw \\ = -\frac{1}{2\pi i} \int_{|w-1|=\epsilon} \frac{4^n}{(1-w)^{n-1} (1+w)^{n+2}} \; dw.$$

Prepare for coefficient extraction. $$-\frac{1}{2\pi i} \int_{|w-1|=\epsilon} \frac{4^n}{(1-w)^{n-1} (2+(w-1))^{n+2}} \; dw \\= -\frac{1}{2\pi i} \int_{|w-1|=\epsilon} \frac{4^n}{2^{n+2}} \frac{1}{(1-w)^{n-1} (1+(w-1)/2)^{n+2}} \; dw \\= \frac{1}{2\pi i} \int_{|w-1|=\epsilon} 2^{n-2} \frac{(-1)^n}{(w-1)^{n-1}} \sum_{q\ge 0} {q+n+1\choose n+1} (-1)^q \frac{(w-1)^q}{2^q} \; dw.$$

We need the coefficient $[(w-1)^{n-2}]$ which is $$2^{n-2} (-1)^n {n-2+n+1\choose n+1} (-1)^{n-2} \frac{1}{2^{n-2}} = {2n-1\choose n+1}$$ or alternatively $${2n-1\choose n-2}.$$

-