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

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

\begin{align*} \text{from}&\qquad&\sum_{j=0}^n\binom{n}{j}a_j&=[z^n]\frac{1}{1-z}A\left(\frac{z}{1-z}\right)\\ \text{to}&\qquad&\sum_{j=0}^n\binom{n+pj}{m+qj}a_j&=[z^n]\frac{z^m}{(1-z)^{m+1}}A\left(\frac{z^{q-p}}{(1-z)^q}\right)\qquad q>p\tag{1} \end{align*}

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 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)}\,.$$

Tags:

Combinatorics

Binomial Coefficients

Summation

Complex Analysis

Analytic Combinatorics

Related

Is this function necessarily a polynomial? How to evaluate the integral $\int \sqrt{1+\sin(x)} dx$ Showing that $T:V\to V$ has a cyclic vector if its eigenspaces all have dimension one. Checking that a torsion-free abelian group has finite rank The multiplicative groups $\mathbb{Q}^\ast$ and $\mathbb{R}^\ast$ are not isomorphic limit $\lim_{n\to ∞}\sin(\pi(2+\sqrt3)^n)$ Convergence of $\sum_n \frac{|\sin(n^2)|}{n}$ Does any given integer only occur in one primitive Pythagorean triple? How to prove each element of the following sequence is a perfect square? If $\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}=1$, what can we say about $\frac{a^2}{b+c}+\frac{b^2}{c+a}+\frac{c^2}{a+b}$? Number of Dyck Paths that touch the diagonal exactly $k$ times? What is $\int_0^1 \frac{\log \left(1-x^2\right) \sin ^{-1}(x)^2}{x^2} \, dx$?

Recent Posts