Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was looking at the mathworld entry for Catalan Numbers http://mathworld.wolfram.com/CatalanNumber.html and was surprised to find formula (11) there:

(1) $C_n= \sum_{k=0}^n (-1)^k 2^{n-k}\binom{n}{k}\binom{k}{\lfloor k/2\rfloor}$

where $C_n=\frac{1}{n+1}\binom{2n}{n}$ is the $n$-th Catalan number.

I tried to prove that formula but failed. One thing that I tried is the following. Define $D_n = \binom{n}{\lfloor n/2 \rfloor}$, then formula (1) states that $(C_n/2^n)_n$ is the (alternating) binomial transform of $(D_k/2^k)_k$. Since the alternating binomial transform is self-inverse. Proving (1) is equivalent to proving the following

(2) $\binom{n}{\lfloor n/2 \rfloor}=D_n = \sum_{k=0}^n (-1)^k 2^{n-k} \binom{n}{k}C_k$

I haven't been able to prove this formula either.

Could anyone help me find a proof for them?

share|improve this question

1 Answer 1

Since this question has not been answered I will try to give an answer here.

Suppose we are trying to show that $$\sum_{k=0}^n {n\choose k} (-1)^k 2^{n-k} {k\choose \lfloor k/2 \rfloor} = C_n$$ where $C_n = \frac{1}{n+1}{2n\choose n}$ is the $n$-th Catalan number.

Introduce the integral representation $${k\choose \lfloor k/2 \rfloor} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^k}{z^{\lfloor k/2 \rfloor+1}} \; dz.$$

This gives the following integral for the sum: $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z} \sum_{k=0}^n {n\choose k} (-1)^k 2^{n-k} \frac{(1+z)^k}{z^{\lfloor k/2 \rfloor}} \; dz.$$

This integral has two components, call them $A$ and $B$. Component $A$ is $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z} \sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k} 2^{n-2k} \frac{(1+z)^{2k}}{z^k} \; dz.$$ This is $$2^{n-1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z} \left(\left(1+\frac{1+z}{2\sqrt{z}}\right)^n + \left(1-\frac{1+z}{2\sqrt{z}}\right)^n \right) \; dz.$$

Component $B$ is $$-\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z} \sum_{k=0}^{\lceil n/2\rceil-1} {n\choose 2k+1} 2^{n-2k-1} \frac{(1+z)^{2k+1}}{z^k} \; dz.$$ This is $$-2^{n-1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{\sqrt{z}}{z} \left(\left(1+\frac{1+z}{2\sqrt{z}}\right)^n - \left(1-\frac{1+z}{2\sqrt{z}}\right)^n \right) \; dz.$$

Use the substitution $z=w^2$ where $dz = 2w\; dw$ on both components to get for A $$\frac{1}{2} 2^{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^2} \left(\left(1+\frac{1+w^2}{2w}\right)^n + \left(1-\frac{1+w^2}{2w}\right)^n \right) 2w \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n+1}} \frac{1}{2} \left(\left(1+w\right)^{2n} + (-1)^n \left(1-w\right)^{2n} \right) \; dw.$$ The factor of $1/2$ in front accounts for the fact that $z$ must circle the origin twice for $w$ to circle it once. Extracting coefficients we get for component $A$ $$\frac{1}{2} {2n\choose n} + \frac{1}{2} (-1)^n (-1)^n {2n\choose n} = {2n\choose n}.$$

We get for component $B$ the integral $$-\frac{1}{2} 2^{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{w}{w^2} \left(\left(1+\frac{1+w^2}{2w}\right)^n - \left(1-\frac{1+w^2}{2w}\right)^n \right) 2w \; dw \\ = -\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^n} \frac{1}{2} \left(\left(1+w\right)^{2n} - (-1)^n \left(1-w\right)^{2n} \right) \; dw.$$ Extracting coefficients we get for component $B$ $$-\frac{1}{2} {2n\choose n-1} + \frac{1}{2} (-1)^n (-1)^{n-1} {2n\choose n-1} = - {2n\choose n-1}.$$ Finally collecting the contributions from both components we get for our result $${2n\choose n} - {2n\choose n-1} = {2n\choose n} - \frac{n}{n+1} {2n\choose n} = \frac{1}{n+1} {2n\choose n}$$ as claimed.

We have not made use of the properties of complex integrals here so this computation can also be presented using just algebra of generating functions.

Apparently this method is due to Egorychev although some of it is probably folklore.

Addendum. It appears we can treat the second equation with the same method. Suppose we are trying to show that $${n\choose \lfloor n/2\rfloor} = \sum_{k=0}^n {n\choose k} (-1)^k 2^{n-k} C_k$$ where $C_n = \frac{1}{n+1}{2n\choose n}$ is the $n$-th Catalan number.

Introduce the integral representation $${2k\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2k}}{z^{k+1}} \; dz.$$

This gives for the sum the integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z} \sum_{k=0}^n {n\choose k} (-1)^k 2^{n-k} \frac{1}{k+1} \frac{(1+z)^{2k}}{z^k} \; dz \\ = 2^n \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z} \sum_{k=0}^n {n\choose k} (-1)^k 2^{-k} \frac{1}{k+1} \frac{(1+z)^{2k}}{z^k} \; dz.$$

Now we have that $$\left(\sum_{k=0}^n {n\choose k} \frac{1}{k+1} x^{k+1}\right)' = \sum_{k=0}^n {n\choose k} x^k = (1+x)^n = \left(\frac{1}{n+1} (1+x)^{n+1}\right)'$$ and therefore $$\sum_{k=0}^n {n\choose k} \frac{1}{k+1} x^k = \frac{1}{x} \frac{1}{n+1} \left(-1 + (1+x)^{n+1}\right).$$

In the sum integral we have $$x = - \frac{(1+z)^2}{2z}$$ so we get for the integral $$- 2^n \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z} \frac{2z}{(1+z)^2} \frac{1}{n+1} \left(-1 + \left(1 - \frac{(1+z)^2}{2z}\right)^{n+1}\right)\; dz \\ = - \frac{2^{n+1}}{n+1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1+z)^2} \left(-1 + \left(1 - \frac{(1+z)^2}{2z}\right)^{n+1}\right)\; dz .$$

The first component of this integral is $$\frac{2^{n+1}}{n+1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1+z)^2} \; dz = 0.$$

That leaves the second component which is $$- \frac{2^{n+1}}{n+1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1+z)^2} \left(1 - \frac{(1+z)^2}{2z}\right)^{n+1} \; dz \\ = - \frac{1}{n+1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1+z)^2} \left(2 - \frac{(1+z)^2}{z}\right)^{n+1} \; dz \\ = - \frac{1}{n+1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{(1+z)^2} \left(2z - (1+z)^2\right)^{n+1} \; dz \\ = \frac{(-1)^n}{n+1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{(1+z)^2} \left(1+z^2\right)^{n+1} \; dz.$$

Extracting coefficients from this yields $$\frac{(-1)^n}{n+1} \sum_{q=0}^{\lfloor n/2\rfloor} {n+1\choose q} (-1)^{n-2q} (n-2q+1) = \frac{1}{n+1} \sum_{q=0}^{\lfloor n/2\rfloor} {n+1\choose q} (n-2q+1) \\ = \sum_{q=0}^{\lfloor n/2\rfloor} {n+1\choose q} - \frac{2}{n+1} \sum_{q=1}^{\lfloor n/2\rfloor} {n+1\choose q} q \\ = \sum_{q=0}^{\lfloor n/2\rfloor} {n+1\choose q} - 2 \sum_{q=1}^{\lfloor n/2\rfloor} \frac{n!}{(q-1)!(n-(q-1))!} \\ = \sum_{q=0}^{\lfloor n/2\rfloor} {n+1\choose q} - 2 \sum_{q=1}^{\lfloor n/2\rfloor} {n\choose q-1} \\ = \sum_{q=0}^{\lfloor n/2\rfloor} {n+1\choose q} - 2 \sum_{q=0}^{\lfloor n/2\rfloor-1} {n\choose q} .$$

Now there are two cases. Suppose first that $n=2m$ to get $$\sum_{q=0}^m {2m+1\choose q} - 2 \sum_{q=0}^{m-1} {2m\choose q} = \frac{1}{2} 2^{2m+1} - 2 \times \frac{1}{2} \left(2^{2m} - {2m\choose m} \right) = {2m\choose m}.$$ The second case is $n$ odd so that $n=2m+1$ and we get $$\sum_{q=0}^m {2m+2\choose q} - 2 \sum_{q=0}^{m-1} {2m+1\choose q} \\ = \frac{1}{2} \left(2^{2m+2} - {2m+2\choose m+1}\right) - 2 \times \frac{1}{2} \left(2^{2m+1} - {2m+1\choose m} - {2m+1\choose m+1}\right) \\ = {2m+1\choose m} + {2m+1\choose m+1} - \frac{1}{2} {2m+2\choose m+1} \\ = 2{2m+1\choose m} - \frac{1}{2} \frac{2m+2}{m+1} {2m+1\choose m+1} = {2m+1\choose m}.$$

We can join these two answer to produce the desired result, which is $${n\choose \lfloor n/2\rfloor}.$$

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