# Looking for a short proof of a harmless looking binomial identity

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

• I think it would be beneficial to include your own derivation within the question body/as an answer? Mar 16, 2020 at 17:19
• @mrtaurho: I've added the proof. Mar 16, 2020 at 17:27
• If you multiply both sides of the identity by $2$ and rewrite the identity in terms of the variables $N=2n$, $r=n-k$ you get $$2\sum_j\binom{N}{2r+2j}\binom{r+j}{r}=\binom{N-r}{r}\frac{N}{N-r}2^{N-2r},$$ which appears to hold--I haven't proved it--for odd $N$ as well. Given an $N$-cycle, the right side can be interpreted as the number of ways of choosing both an $r$-matching of the graph and a function from the set consisting of the $N-2r$ unmatched vertices to the set $\{0,1\}$. I don't see at the moment that the left side has the same interpretation. Jun 22, 2020 at 16:28
• One more thing: I believe your identity is essentially the equality of some of the different explicit expressions given here for Chebyshev polynomials of the first kind. Jun 22, 2020 at 17:04
• @WillOrrick: Many thanks for the hints. I find them interesting and I will think about it soon. But at the time I'm busy with your recent post. :-) Jun 22, 2020 at 20:26

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.

• Great, Will! Many thanks for this interesting and instructive answer. ... and this funny application of the PIE. This calls for looking for similar applications of it. Very nice. :-) Jun 24, 2020 at 15:44

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

• Many thanks, Marko . (+1) Good to see, there is more than one way to reach the goal. :-) Mar 16, 2020 at 20:34
• @MarkusScheuer And you don´t have any motivation to accept this answer? Btw, stay healthy. Apr 17, 2020 at 15:54
• @MarkoRiedel: Dear Marko, in fact I was hoping for a substantially different approach. But since there was no such answer given, it's more than fair to accept your answer.. Thanks for your notification. Stay attentive, stay healthy and be in good heart. :-) Apr 17, 2020 at 18:06
• @callculus: I just realised, that the notification was done by you and not by Marko himself. Nice notification, thanks. Stay attentive and stay healthy, too. :-) Apr 17, 2020 at 18:12
• @MarkusScheuer Thank you for the kind wishes and best regards in these special times. Apr 17, 2020 at 21:41