Looking for a short proof of a harmless looking binomial identity

Question

I managed to prove for this MSE post the rather harmless looking binomial identity for natural $1\leq k\leq n$: \begin{align*} \color{blue}{\sum_{j=0}^k\binom{2n}{2j}\binom{n-j}{k-j}=\binom{n+k}{n-k}\frac{4^kn}{n+k}}\tag{1} \end{align*} using the coefficient of operator method. Admittedly, there are a lot of intermediate steps used to show the validity of (1).

Question: I'm wondering if there is a more direct, less lengthy derivation than the one I've provided below.

We obtain for $1\leq k\leq n$: \begin{align*} \color{blue}{\sum_{j=0}^k}&\color{blue}{\binom{2n}{2j}\binom{n-j}{k-j}}\\ &=\sum_{j=0}^n\binom{2n}{2j}\binom{n-j}{n-k}\tag{2}\\ &=\sum_{j=0}^n\binom{2n}{2j}[z^{n-k}](1+z)^{n-j}\tag{3}\\ &=[z^{n-k}](1+z)^n\sum_{j=0}^n\binom{2n}{2j}\frac{1}{(1+z)^j}\\ &=\frac{1}{2}[z^{n-k}](1+z)^n\left(\left(1+\frac{1}{\sqrt{1+z}}\right)^{2n}+\left(1-\frac{1}{\sqrt{1+z}}\right)^{2n}\right)\\ &=\frac{1}{2}[z^{n-k}]\left(\left(1+\sqrt{1+z}\right)^{2n}+\left(1-\sqrt{1+z}\right)^{2n}\right)\\ &=\frac{1}{2}[z^{n-k}]\left(1+\sqrt{1+z}\right)^{2n}\tag{4}\\ &=\frac{1}{2}[z^{-1}]z^{-n+k-1}\left(1+\sqrt{1+z}\right)^{2n}\tag{5}\\ &=\frac{1}{2}[w^{-1}]\left(w^2-1\right)^{n-k-1}(1+w)^{2n}2w\tag{6}\\ &=[w^{-1}]w(w-1)^{-n+k-1}(w+1)^{n+k-1}\\ &=[u^{-1}](u+1)u^{-n+k-1}(u+2)^{n+k-1}\tag{7}\\ &=\left([u^{n-k}]+[u^{n-k-1}]\right)\sum_{j=0}^{n+k-1}\binom{n+k-1}{j}u^j2^{n+k+1-j}\\ &=\binom{n+k-1}{n-k}2^{2k-1}+\binom{n+k-1}{n-k-1}2^{2k}\tag{8}\\ &=\binom{n+k}{n-k}\frac{2k}{n+k}2^{2k-1}+\binom{n+k}{n-k}\frac{n-k}{n+k}2^{2k}\tag{9}\\ &\,\,\color{blue}{=\binom{n+k}{n-k}\frac{4^kn}{n+k}} \end{align*} and the claim follows.

Comment:

• In (2) we use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$. We also set the upper index to $n$ without changing anything, since we are adding zeros only.

• In (3) we use the coefficient of operator method.

• In (4) we skip $\left(1-\sqrt{1+z}\right)^{2n}=cz^{2n}+\cdots$ since it has only powers of $z$ greater than $n$ and does not contribute to $[z^{n-k}]$.

• In (5) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

• In (6) we use the transformation of variable formula $[z^{-1}]f(z)=[w^{-1}]f(g(w))g^\prime(w)$ with $1+z=w^2, \frac{dz}{dw}=2w$.

• In (7) we use the transformation of variable formula again, with $w-1=u, \frac{dw}{du}=1$.

• In (8) we select the coefficients accordingly.

• In (9) we use the binomial identities $\binom{p-1}{q}=\binom{p}{q}\frac{p-q}{p}$ and $\binom{p}{q}=\binom{p-1}{q-1}\frac{p}{q}$.

Answer 1

The result follows from the equality of two different expressions for the Chebyshev polynomials of the first kind. We have $$ \begin{aligned} T_N(x)&=\sum_{j\ge0}\binom{N}{2j}(x^2-1)^j x^{N-2j}\\ &=\frac{1}{2}\sum_{r\ge0}(-1)^r\frac{N}{N-r}\binom{N-r}{r}(2x)^{N-2r}, \end{aligned} $$ where the first equality holds for $N\ge0$ and the second for $N\ge1$. Expanding the binomial factor in the first expression gives $$ \begin{aligned} &\sum_{j\ge0}\binom{N}{2j}\sum_{r=0}^j\binom{j}{r}(-1)^r x^{2j-2r}x^{N-2j}\\ &\quad=\sum_{r\ge0}(-1)^rx^{N-2r}\sum_{j\ge r}\binom{N}{2j}\binom{j}{k}\\ &\quad=\sum_{r\ge0}(-1)^rx^{N-2r}\sum_{j\ge 0}\binom{N}{2r+2j}\binom{r+j}{r}. \end{aligned} $$ Comparing coefficients yields $$ \sum_{j\ge 0}\binom{N}{2r+2j}\binom{r+j}{r}=\frac{1}{2}\frac{N}{N-r}\binom{N-r}{r}2^{N-2r} $$ Setting $N=2n$ and $r=n-k$ gives your identity.

Of course for this to be a proof, we really have to prove that the two expressions for $T_N(x)$ hold. We define $T_N(x)$ by the condition $\cos(N\theta)=T_N(\cos\theta)$. The first expression for $T_N(x)$ follows by taking the real parts of $$ \cos(N\theta)+i\sin(N\theta)=e^{iN\theta}=\sum_{k=0}^N\binom{N}{k}(i\sin(\theta))^k\cos^{N-k}\theta $$ and recognizing that $(i\sin\theta)^{2j}=(\cos^2\theta-1)^j$.

The factor $\frac{N}{N-r}\binom{N-r}{r}$ in the second expression is the number of $r$-matchings on $C_N$, the cycle graph of $N$ vertices. Equivalently, it's the number of ways of placing $r$ non-overlapping dominoes on the edges of an $N$-gon. What does this have to do with expressing $\cos(N\theta)$ as a polynomial in $\cos\theta$? The idea is to add powers of $2\cos\theta=(e^{i\theta}+e^{-i\theta})$ up to the $N^\text{th}$ power, with coefficients chosen so the only the $e^{iN\theta}$ and $e^{-iN\theta}$ terms survive, and then multiply by $\frac{1}{2}$ to get $\cos(N\theta)$. To eliminate the unwanted terms, we use the principle of inclusion-exclusion, as follows. Represent a term in the expansion of $(e^{i\theta}+e^{-i\theta})^N$ by the sequence of signs in the exponent. So the term $e^{i\theta}e^{i\theta}e^{-i\theta}e^{i\theta}$ in the expansion of $(e^{i\theta}+e^{-i\theta})^4$ would be represented by the sign sequence $++-+$. We want to keep the terms $+++\ldots+$ and $---\ldots-$, and discard everything else. Define $S_j$ to the the set of sequences in which a plus at position $j$ is followed by a minus at position $j+1$, where $j$ ranges from $0$ to $N-1$ and $j+1$ is computed $\mod N$ (so that the sequence is considered to be wrapped on a circle). Since the terms $e^{i\theta}$ and $e^{-i\theta}$ at positions $j$ and $j+1$ cancel, the sum of the terms corresponding to sequences in $S_j$ is $(e^{i\theta}+e^{-i\theta})^{N-2}$. So, from $(e^{i\theta}+e^{-i\theta})^N$, we subtract, for each $j$, the quantity $(e^{i\theta}+e^{-i\theta})^{N-2}$. But if a term has a sequence in which $+$ is immediately followed by $-$ at two different positions, say $j$ and $k$, that term will have been subtracted twice, and therefore needs to be added back in. This requires adding $(e^{i\theta}+e^{-i\theta})^{N-4}$ for every such pair $j$, $k$. By the principle of inclusion--exclusion, we continue in this way, alternately adding and subtracting the terms $(e^{i\theta}+e^{-i\theta})^{N-2r}$ corresponding to sequences in $S_{j_1}\cap S_{j_2} \cap S_{j_3}\cap\ldots\cap S_{j_r}$. It only remains to determine how many non-empty intersections there are of $r$ sets. There is only one condition we need to worry about: if $+$ at $j$ is followed by $-$ at $j+1$, then it certainly is not the case that $+$ is followed by $-$ at positions $j+1$ and $j+2$, so any intersection containing $S_j\cap S_{j+1}$ is empty. This is precisely the non-overlapping domino condition, and the second expression for $T_N(x)$ follows.

Answer 2

Here is an alternate solution, where the number of steps is about the same as what OP provided. Could use additional streamlining by removing some of the simpler proceedings. Start as follows:

$$\sum_{j=0}^k {2n\choose 2j} {n-j\choose k-j} = \sum_{j=0}^k {2n\choose 2k-2j} {n-k+j\choose j} \\ = [z^{2k}] (1+z)^{2n} \sum_{j=0}^k z^{2j} {n-k+j\choose j}.$$

Here the coefficient extractor enforces the range:

$$[z^{2k}] (1+z)^{2n} \sum_{j\ge 0} z^{2j} {n-k+j\choose j} \\ = [z^{2k}] (1+z)^{2n} \frac{1}{(1-z^2)^{n-k+1}} = [z^{2k}] (1+z)^{n+k-1} \frac{1}{(1-z)^{n-k+1}}.$$

This is

$$\mathrm{Res}_{z=0} \frac{1}{z^{2k+1}} (1+z)^{n+k-1} \frac{1}{(1-z)^{n-k+1}} \\ = (-1)^{n-k+1} \mathrm{Res}_{z=0} \frac{1}{z^{2k+1}} (1+z)^{n+k-1} \frac{1}{(z-1)^{n-k+1}}.$$

Now the residue at infinity is zero so this is minus the residue at one:

$$(-1)^{n-k} \mathrm{Res}_{z=1} \frac{1}{(1+(z-1))^{2k+1}} (2+(z-1))^{n+k-1} \frac{1}{(z-1)^{n-k+1}} \\ = (-1)^{n-k} \sum_{j=0}^{n-k} {n+k-1\choose j} 2^{n+k-1-j} (-1)^{n-k-j} {n-k-j+2k\choose 2k} \\ = 2^{n+k-1} \sum_{j=0}^{n-k} {n+k-1\choose j} 2^{-j} (-1)^{j} {n+k-j\choose n-k-j}.$$

Coefficient extractor enforces range:

$$2^{n+k-1} [z^{n-k}] (1+z)^{n+k} \sum_{j\ge 0} {n+k-1\choose j} 2^{-j} (-1)^{j} \frac{z^j}{(1+z)^j} \\ = 2^{n+k-1} [z^{n-k}] (1+z)^{n+k} \left(1-\frac{z}{2(1+z)}\right)^{n+k-1} \\ = [z^{n-k}] (1+z) (2+z)^{n+k-1} \\ = [z^{n-k}] (2+z)^{n+k-1} + [z^{n-k-1}] (2+z)^{n+k-1} \\ = {n+k-1\choose n-k} 2^{n+k-1-(n-k)} + {n+k-1\choose n-k-1} 2^{n+k-1-(n-k-1)} \\ = \frac{1}{2} 4^k \frac{2k}{n+k} {n+k\choose n-k} + \frac{n-k}{n+k} 4^k {n+k\choose n-k} \\ = \frac{4^k n}{n+k} {n+k\choose n-k}.$$