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 was looking at the mathworld entry for Catalan Numbers 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|cite|improve this question

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|cite|improve this answer

Here is another variant to proof OPs claim. As he already stated, it is sufficient to proof the first identity since the other follows immediately.

Let $C_n$ be the $n$-th Catalan number. The following holds true \begin{align*} C_n&=\sum_{k=0}^n(-1)^k2^{n-k}\binom{n}{k}\binom{k}{\left\lfloor\frac{k}{2}\right\rfloor}\qquad\qquad n\geq 0\tag{1}\\ \end{align*}

We separate the positive and negative terms in (1) and write the sum as \begin{align*} \sum_{k=0}^n&(-1)^k2^{n-k}\binom{n}{k}\binom{k}{\left\lfloor\frac{k}{2}\right\rfloor}\\ &=\sum_{k=0}^n\binom{n}{2k}\binom{2k}{k}2^{n-2k} -\sum_{k=0}^n\binom{n}{2k+1}\binom{2k+1}{k}2^{n-2k-1}\tag{2} \end{align*}

Note that the Catalan Numbers $C_n=\frac{1}{n+1}\binom{2n}{n}$ can be written as \begin{align*} C_n=\binom{2n}{n}-\binom{2n}{n+1}\tag{3} \end{align*}

It's a nice circumstance that we can directly relate this representation with the sums of the RHS in (2). We will show the following holds true for $n\geq 0$

\begin{align*} \sum_{k=0}^n&\binom{n}{2k}\binom{2k}{k}2^{n-2k}=\binom{2n}{n}\tag{4}\\ \sum_{k=0}^n&\binom{n}{2k+1}\binom{2k+1}{k}2^{n-2k-1}=\binom{2n}{n+1}\tag{5} \end{align*}

$$ $$

First part: Generating function for $\binom{2n}{n}$ and functional relation

We denote with $f(x)$ the well known generating function of the central binomial coefficients. Note that \begin{align*} f(x)=\frac{1}{\sqrt{1-4x}}=\sum_{n\geq 0}\binom{-\frac{1}{2}}{n}(-4x)^n =\sum_{n\geq 0}\binom{2n}{n}x^n \end{align*} We can now derive a functional relation by evaluating $f$ at $\frac{x^2}{(1-2x)^2}$. We obtain \begin{align*} f\left(\frac{x^2}{(1-2x)^2}\right)=\frac{1}{\sqrt{1-4\frac{x^2}{(1-2x)^2}}} =\frac{1-2x}{\sqrt{1-4x}} \end{align*} and we conclude \begin{align*} f(x)=\frac{1}{1-2x}f\left(\frac{x^2}{(1-2x)^2}\right)=\frac{1}{\sqrt{1-4x}}\tag{6} \end{align*} We use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series. We obtain from (6) for $n\geq 0$ \begin{align*} [x^n]f(x)&=[x^n]\frac{1}{1-2x}f\left(\frac{x^2}{(1-2x)^2}\right)\\ &=[x^n]\sum_{k\geq 0}\binom{2k}{k}\frac{x^{2k}}{(1-2x)^{2k+1}}\\ &=[x^n]\sum_{k\geq 0}\binom{2k}{k}x^{2k}\sum_{l\geq 0}\binom{-(2k+1)}{l}(-2x)^l\\ &=[x^n]\sum_{k\geq 0}\binom{2k}{k}x^{2k}\sum_{l\geq 0}\binom{2k+l}{l}(2x)^l\\ &=\sum_{k\geq 0}\binom{2k}{k}[x^{n-2k}]\sum_{l\geq 0}\binom{2k+l}{l}(2x)^l\\ &=\sum_{k\geq 0}\binom{n}{2k}\binom{2k}{k}2^{n-2k}\\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\Box \end{align*}

and (4) follows.

$$ $$

Second part: Generating function for $\binom{2n}{n+1}$ and functional relation

Similarly to the first part we define a function $g(x)$ to be the generating function for $\binom{2n}{n+1}$. Since the generating function $C(x)$ for the Catalan numbers $C_n$ is known to be \begin{align*} C(x)=\frac{1}{2x}\left(1-\sqrt{1-4x}\right) \end{align*} it follows from relation (3) \begin{align*} g(x)&=\sum_{k\geq 0}\binom{2n}{n+1}x^n =\frac{1}{\sqrt{1-4x}}-\frac{1}{2x}\left(1-\sqrt{1-4x}\right)\\ &=\frac{1}{2x}\left(\frac{2x-1}{\sqrt{1-4x}}+1\right)\tag{7} \end{align*}

Now we proceed slightly different to (1). We consider the generating function $p(x)$ with \begin{align*} p(x)&=\sum_{k\geq 0}\binom{2k+1}{k}x^{2k}\\ &=\sum_{k\geq 0}(2k+1)C_kx^{2k}\\ &=D\left(\sum_{k\geq 0}C_kx^{2k+1}\right)\\ &=D\left(\frac{1-\sqrt{1-4x^2}}{2x}\right)\\ &=\frac{1}{2x^2}\left(\frac{1}{\sqrt{1-4x^2}}-1\right) \end{align*} with $D$ the differential operator. Evaluating $p$ at $\frac{x}{1-2x}$ results in \begin{align*} p\left(\frac{x}{1-2x}\right)&=\frac{1}{2\left(\frac{x}{1-2x}\right)^2} \left(\frac{1}{\sqrt{1-4\left(\frac{x}{1-2x}\right)^2}}-1\right)\\ &=\frac{(1-2x)^2}{2x^2}\left(\frac{1-2x}{\sqrt{1-4x}}-1\right) \end{align*} We compare this expression with $g(x)$ in (7) and observe \begin{align*} g(x)=\frac{x}{(1-2x)^2}p\left(\frac{x}{1-2x}\right) \end{align*} Expanding the RHS of the last equation we obtain \begin{align*} [x^n]g(x)&=[x^n]\frac{x}{(1-2x)^2}p(\frac{x}{1-2x})\\ &=[x^n]x\sum_{k\geq 0}\binom{2k+1}{k}\frac{x^{2k}}{(1-2x)^{2k}+2}\\ &=[x^n]\sum_{k\geq 0}\binom{2k+1}{k}x^{2k+1}\sum_{l\geq 0}\binom{-(2k+2)}{l}(-2x)^l\\ &=[x^n]\sum_{k\geq 0}\binom{2k+1}{k}x^{2k+1}\sum_{l\geq 0}\binom{2k+1+l}{l}(2x)^l\\ &=\sum_{k\geq 0}\binom{2k+1}{k}[x^{n-2k-1}]\sum_{l\geq 0}\binom{2k+1+l}{l}(2x)^l\\ &=\sum_{k\geq 0}\binom{n}{2k+1}\binom{2k+1}{k}2^{n-2k-1}\\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\Box \end{align*} and (5) follows, which completes the proof.

Note: I found the functional equation of $f$ which is the essence of the proof in J. Riordans classic Combinatorial Identities.

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.