Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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...

share|cite|improve this question
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] $$

share|cite|improve this answer

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*}$$


$$\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.

share|cite|improve this answer

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

share|cite|improve this answer

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}.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.