# Prove that $\sum\limits_{j=k}^n\,(-1)^{j-k}\,\binom{j}{k}\,\binom{2n-j}{j}\,2^{2(n-j)}=\binom{2n+1}{2k+1}$.

In an attempt to answer this thread, I discovered an identity involving binomial coefficients. However, I am not able to find a proof. All tricks are welcome.

Let $n$ and $k$ be nonnegative integers with $k\leq n$. Prove that $$\sum\limits_{j=k}^n\,(-1)^{j-k}\,\binom{j}{k}\,\binom{2n-j}{j}\,2^{2(n-j)}=\binom{2n+1}{2k+1}\,.$$

• Very nice question with very nice answers, I upvoted all the upvotable here :D – Jack D'Aurizio Aug 26 '16 at 23:24

Suppose we seek to show that

$$\sum_{q=k}^n (-1)^{q-k} {q\choose k} {2n-q\choose q} 2^{2(n-q)} = {2n+1\choose 2k+1}.$$

Re-index to get

$$\sum_{q=0}^{n-k} (-1)^{q} {q+k\choose k} {2n-k-q\choose k+q} 2^{2(n-k-q)}.$$

Introduce

$${2n-k-q\choose k+q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n-2k-2q+1}} \frac{1}{(1-z)^{k+q+1}} \; dz.$$

Observe that this vanishes when $q\gt n-k$ so it provides range control and we may extend $q$ to infinity, getting for the sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n-2k+1}} \frac{1}{(1-z)^{k+1}} \sum_{q\ge 0} (-1)^q {q+k\choose q} \frac{z^{2q}}{(1-z)^q} 2^{2(n-k-q)} \; dz \\ = \frac{2^{2(n-k)}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n-2k+1}} \frac{1}{(1-z)^{k+1}} \frac{1}{(1+z^2/(1-z)/2^2)^{k+1}} \; dz \\ = \frac{2^{2(n-k)}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n-2k+1}} \frac{1}{(1-z+z^2/2^2)^{k+1}} \; dz \\ = \frac{2^{2n+2}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n-2k+1}} \frac{1}{(4-4z+z^2)^{k+1}} \; dz \\ = \frac{2^{2n+2}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n-2k+1}} \frac{1}{(z-2)^{2k+2}} \; dz \\ = \frac{2^{2n-2k}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n-2k+1}} \frac{1}{(z/2-1)^{2k+2}} \; dz \\ = \frac{(-1)^{2k+2} 2^{2n-2k}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n-2k+1}} \frac{1}{(1-z/2)^{2k+2}} \; dz.$$

This is

$$2^{2n-2k} [z^{2n-2k}] \frac{1}{(1-z/2)^{2k+2}} = 2^{2n-2k} {2n-2k+2k+1\choose 2k+1} \frac{1}{2^{2n-2k}} \\ = {2n+1\choose 2k+1}$$

which is the claim.

Remark. We discover having reached the end of the computation that we never needed to substitute the variable in the integral, which means it could be done using formal power series and the coefficient-of method.

It's convenient to use the coefficient of operator $[z^j]$ to denote the coefficient of $z^j$ in a series. This way we can write e.g. \begin{align*} [z^j](1+z)^n=\binom{n}{j} \end{align*}

We recall the Euler transformation formula of a series \begin{align*} A(z)=\sum_{n= 0}^\infty a_nz^n\qquad\qquad \frac{1}{1-z}A\left(\frac{z}{1-z}\right)=\sum_{n= 0}^\infty \left(\sum_{j=0}^n\binom{n}{j}a_j\right)z^n \end{align*} This transformation formula together with a proof can be found e.g. in Harmonic Number Identities Via Euler's transform by K.N. Boyadzhiev.

This formula is useful, but it can be considerably generalized

A proof of (1) can be found in Theorem 2.1 in Riordan arrays and combinatorial sums by R. Sprugnoli.

We can now show:

The following is valid \begin{align*} \sum_{j=k}^n(-1)^{j-k}\binom{j}{k}\binom{2n-j}{j}2^{2(n-j)}=\binom{2n+1}{2k+1}\tag{2} \end{align*}



We start by rearranging the left hand side of (2) \begin{align*} \sum_{j=k}^n&(-1)^{j-k}\binom{j}{k}\binom{2n-j}{j}2^{2(n-j)}\\ &=(-1)^k4^n\sum_{j=k}^n\binom{2n-j}{j}\binom{j}{k}\left(-\frac{1}{4}\right)^j\tag{3} \end{align*}

In order to use (1) we derive a generating function $A(z)$ for \begin{align*} a_j=\binom{j}{k}\left(-\frac{1}{4}\right)^j \end{align*} We obtain \begin{align*} A(z)&=\sum_{j= 0}^\infty a_jz^j\\ &=\sum_{j=k}^\infty\binom{j}{k}\left(-\frac{1}{4}\right)^jz^j\\ &=\sum_{j=0}^\infty\binom{j+k}{j}\left(-\frac{1}{4}\right)^{j+k}z^{j+k}\tag{4}\\ &=\left(-\frac{z}{4}\right)^k\sum_{j=0}^\infty\binom{-k-1}{j}\left(\frac{z}{4}\right)^{j}\tag{5}\\ &=\frac{\left(-\frac{z}{4}\right)^k}{\left(1+\frac{z}{4}\right)^{k+1}}\tag{6} \end{align*}

Comment:

• In (4) we shift the index so that $j$ starts from $0$.

• In (5) we apply the binomial identity $\binom{-u}{v}=\binom{u+v-1}{v}(-1)^v$.

• In (6) we apply the binomial series expansion.

Since we have derived $A(z)$ we can proceed with the main calculation.

We obtain from (3) and (6) \begin{align*} (-1)^k4^n&\sum_{j=k}^n\binom{2n-j}{j}\binom{j}{k}\left(-\frac{1}{4}\right)^{j}\\ &=(-1)^k4^n[z^{2n}]\frac{1}{1-z}A\left(\frac{z^2}{1-z}\right)\tag{7}\\ &=(-1)^k4^n[z^{2n}]\frac{1}{1-z}\left(-\frac{z^2}{4(1-z)}\right)^k\frac{1}{\left(1+\frac{z^2}{4(1-z)}\right)^{k+1}}\tag{8}\\ &=4^{n-k}[z^{2n-2k}]\frac{1}{\left(1-z+\frac{z^2}{4}\right)^{k+1}}\tag{9}\\ &=4^{n-k}[z^{2n-2k}]\frac{1}{\left(1-\frac{z}{2}\right)^{2(k+1)}}\\ &=4^{n-k}[z^{2n-2k}]\sum_{j=0}^\infty\binom{-2k-2}{j}\left(-\frac{z}{2}\right)^j\tag{10}\\ &=4^{n-k}[z^{2n-2k}]\sum_{j=0}^\infty\binom{2k+j-1}{j}\left(\frac{z}{2}\right)^j\tag{11}\\ &=4^{n-k}\binom{2n+1}{2n-2k}\frac{1}{4^{n-k}}\tag{12}\\ &=\binom{2n+1}{2k+1} \end{align*} and the claim follows.

Comment:

• In (7) we use the representation (1) with the parameter settings $(n,m,p,q)\rightarrow (2n,0,-1,1)$.

• In (8) we use the representation (6) of $A(z)$.

• In (9) we do some simplifications and use the rule $[z^{u+v}]A(z)=[z^u]z^{-v}A(z)$.

• In (10) we apply the binomial series expansion.

• In (11) we use the binomial identity $\binom{-u}{v}=\binom{u+v-1}{v}(-1)^v$.

• In (12) we select the coefficient of $z^{2n-2k}$.

• I will check this in detail later but it looks like we are building an instructive page here. (+1). – Marko Riedel Aug 24 '16 at 21:46
• @MarkoRiedel: Thanks for your nice comment! :-) (+1) – Markus Scheuer Aug 24 '16 at 21:47
• Very interesting in fact. It appears the two approaches produced the same generating function (I guess that is how it ought to be), – Marko Riedel Aug 24 '16 at 21:50

I have found my own mostly combinatorial proof. Write $[m]:=\{1,2,\ldots,m\}$ for every nonnegative integer $m$. There are $\dbinom{2n+1}{2k+1}$ subsets $S$ of $[2n+1]$ of size $2k+1$. We shall count the number of such sets given that the $(k+1)$-st largest element is $2n+1-s$ for some $s\in\{0,1,2,\ldots,2n\}$. There are $k$ elements left to choose from $[2n-s]$, which can be done in $\dbinom{2n-s}{k}$ ways. There are also $k$ elements to choose from $[2n+1]\setminus[2n+1-s]$, which can be done in $\dbinom{s}{k}$ ways. Hence, $$\binom{2n+1}{2k+1}=\sum_{s=0}^{2n}\,\binom{s}{k}\,\binom{2n-s}{k}=\sum_{s=k}^{2n-k}\,\binom{s}{k}\,\binom{2n-s}{k}\,.\tag{*}$$

Now, write $\dbinom{2n-s}{k}=\dbinom{2n-s}{s-(s-k)}$ for $s\geq k$. Using the identity (2) from the answer here, which has a combinatorial proof, we obtain \begin{align} \dbinom{2n-s}{k}&=\sum_{r=0}^{s-k}\,(-1)^r\,\binom{s-k}{r}\,\binom{(2n-s)+(s-k)-r}{s} \\&=\sum_{r=0}^{s-k}\,(-1)^r\,\binom{s-k}{r}\binom{2n-k-r}{s}\,. \end{align} Thus, (*) becomes $$\binom{2n+1}{2k+1}=\sum_{s=k}^{2n-k}\,\binom{s}{k}\,\sum_{r=0}^{s-k}\,(-1)^r\,\binom{s-k}{r}\,\binom{2n-k-r}{s}\,.$$ Let $j:=r+k$. We have $$\binom{2n+1}{2k+1}=\sum_{j=k}^n\,(-1)^{j-k}\,\sum_{s=j}^{2n-k}\,\binom{s}{k}\,\binom{s-k}{j-k}\,\binom{2n-j}{s}\,.$$

Note that $\dbinom{s}{k}\,\dbinom{s-k}{j-k}=\dbinom{s}{j}\,\dbinom{j}{k}$. Ergo, $$\binom{2n+1}{2k+1}=\sum_{j=k}^n\,(-1)^{j-k}\,\binom{j}{k}\,\sum_{s=j}^{2n-k}\,\binom{s}{j}\,\binom{2n-j}{s}\,.$$ Again, we have $\dbinom{s}{j}\,\dbinom{2n-j}{s}=\dbinom{2n-j}{j}\,\dbinom{2(n-j)}{s-j}$, whence $$\binom{2n+1}{2k+1}=\sum_{j=k}^n\,(-1)^{j-k}\,\binom{j}{k}\,\dbinom{2n-j}{j}\,\sum_{s=j}^{2n-k}\,\binom{2(n-j)}{s-j}\,.$$ Finally, $\sum\limits_{s=j}^{2n-k}\,\dbinom{2(n-j)}{s-j}=\sum\limits_{s=j}^{2n-j}\,\dbinom{2(n-j)}{s-j}=2^{2(n-j)}$ leads to $$\binom{2n+1}{2k+1}=\sum_{j=k}^n\,(-1)^{j-k}\,\binom{j}{k}\,\dbinom{2n-j}{j}\,2^{2(n-j)}\,.$$

Here is another variation of the theme. It is convenient to use the coefficient of operator $[z^j]$ to denote the coefficient of $z^j$ in a series. This way we can write e.g. \begin{align*} [z^j](1+z)^n=\binom{n}{j} \end{align*}

We obtain \begin{align*} \sum_{q=k}^n&(-1)^{q-k}\binom{q}{k}\binom{2n-q}{q}4^{n-q}\\ &=\sum_{q=0}^{n-k}(-1)^q\binom{k+q}{q}\binom{2n-k-q}{k+q}4^{n-k-q}\tag{1}\\ &=\sum_{q=0}^{n-k}\binom{-k-1}{q}\binom{-(k+q+1)}{2n-2k-2q}4^{n-k-q}\tag{2}\\ &=\sum_{q=0}^\infty[z^q](1+z)^{-(k+1)}[u^{2n-2k-2q}](1+u)^{-(k+q+1)}4^{n-k-q}\tag{3}\\ &=4^{n-k}[u^{2n-2k}](1+u)^{-(k+1)}\sum_{q=0}^\infty\left(\frac{u^2}{4(1+u)}\right)^q[z^q](1+z)^{-(k+1)}\tag{4}\\ &=4^{n-k}[u^{2n-2k}](1+u)^{-(k+1)}\left(1+\frac{u^2}{4(1+u)}\right)^{-(k+1)}\tag{5}\\ &=4^{n-k}[u^{2n-2k}]\left(1+\frac{u}{2}\right)^{-2(k+1)}\tag{6}\\ &=4^{n-k}[u^{2n-2k}]\sum_{q=0}^{\infty}\binom{-2k-2}{q}\left(\frac{u}{2}\right)^q\tag{7}\\ &=4^{n-k}[u^{2n-2k}]\sum_{q=0}^{\infty}\binom{2k+q+1}{q}\left(-\frac{u}{2}\right)^q\tag{8}\\ &=\binom{2n+1}{2n-2k}\tag{9}\\ &=\binom{2n+1}{2k+1} \end{align*} and the claim follows.

Comment:

• In (1) we shift the index $q$ to start from $0$.

• In (2) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (3) we apply the coefficient of operator twice and we extend the upper limit of the sum to $\infty$ without changing anything, since we are adding zeros only.

• In (4) we use the linearity of the coefficient of operator and apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

• In (5) we use the substitution rule with $z=\frac{u^2}{4(1+u)}$ \begin{align*} A(u)=\sum_{q=0}^\infty a_qu^q=\sum_{q=0}^\infty u^q[z^q]A(z)\\ \end{align*}

• In (6) we do some simplifications.

• In (7) we apply the binomial series expansion.

• In (8) we use again the binomial identity as in (2).

• In (9) we select the coefficient of $u^{2n-2k}$.