# Proof of a combinatorial identity (possibly using trigonometric identities)

For integers $n \geq k \geq 0$, can anyone provide a proof for the following identity?

$$\sum_{j=0}^k\left(\begin{array}{c}2n+1\\\ 2j\end{array}\right)\left(\begin{array}{c}n-j\\\ k-j\end{array}\right) = 2^{2k} \left(\begin{array}{c} n+k\\\ 2k \end{array}\right)$$

I've verified this identity numerically for many values of $n$ and $k$, and suspect it to be true.

I found similar identities in http://www.math.wvu.edu/~gould/Vol.6.PDF, most notably:

$$\sum_{j=0}^k\left(\begin{array}{c}2n\\\ 2j\end{array}\right)\left(\begin{array}{c}n-j\\\ k-j\end{array}\right) = 2^{2k} \frac{n}{n+k}\left(\begin{array}{c} n+k\\\ 2k \end{array}\right)$$

which is Eq. (3.20) in the above link, and

$$\sum_{j=0}^k\left(\begin{array}{c}2n+1\\\ 2j+1\end{array}\right)\left(\begin{array}{c}n-j\\\ k-j\end{array}\right) = 2^{2k} \frac{2n+1}{n-k}\left(\begin{array}{c} n+k\\\ 2k+1 \end{array}\right)$$

which is Eq. (3.34) in the above link. The derivations of these two identities seem to rely on trigonometric identities, which I've been having trouble reconstructing.

• math.upenn.edu/~wilf/AeqB.html – Steve Huntsman Jul 30 '12 at 18:12
• Maple knows this one: > sum(binomial(2*n+1,2*j)*binomial(n-j,k-j),j=0..k) assuming k::nonnegint, n::nonnegint,n>=k; $${\frac {{2}^{2\,k}\Gamma \left( 1+k+n \right) }{\Gamma \left( 2\,k+1 \right) \Gamma \left( n-k+1 \right) }}$$ – Robert Israel Jul 30 '12 at 19:51

I'm surprised no one has posted a proof by double counting yet. First, I will rewrite the sum as $$F(n,k)=\sum_{j=0}^k\binom{2n+1}{2n-2j+1}\binom{n-j}{n-k}.$$ This counts the number of ways I can pick $2n-2j+1$ squares out of a $1\times (2n+1)$ grid, color them alternately black, white, black... etc. and then place a mark on $n-k$ white squares.

By deleting the first square as well as any immediate square following a marked white square we end up with a sequence of $n+k$ squares, $n-k$ of which are marked white squares and several others are colored.

Another way to count this is to choose the marked white squares first. This can be done in $\binom{n+k}{n-k}$ ways. And then specify the unmarked colored squares, this can be done in $2^{2k}$ ways. We get that $$F(n,k)=2^{2k}\binom{n+k}{n-k}$$ which is what we wanted.

Notice that I've left it as an exercise to show that deleting the squares is actually a bijection between the two sets, but this is quite easy to show. Indeed you only have to worry about adding back a square and deciding whether it should be colored or not. This can be done with a parity check on the number of colored boxes between consecutive marked boxes.

• Interpreting specify the unmarked colored squares, this can be done in $2^{2k}$ ways' as meaning we choose an arbitrary subset of the $n-k$ unmarked squares to be (say) black, I can't see how this works. If two adjacent squares are chosen to be black then the marked colouring of $n-k$ squares is not in the image of the 'delete-after-marked-white' map. For a concrete example, take $n=2$ and $k=1$, so $\binom{5}{5}\binom{2}{1} + \binom{5}{3}\binom{1}{1} = 2^2\binom{3}{1}$. Writing $C$ for a marked white square, $CBB$ is not in the image, and neither is $BCW$. What am I misunderstanding? – Mark Wildon Aug 27 '18 at 10:29
• @MarkWildon Notice that some squares can be uncolored. So, in your notation if we denote an uncolored box by $U$ and a colored box by $V\in \{W,B\}$, we have exactly one word of the form $CVV, CVU, CUV, CUU, \dots$ etc. The only word of the form $CVV$, for example, is $CWB$ coming from deleting squares in $BCBWB$. The only word of the form $CVU$ is $CBU$ coming from deleting squares in $BCUBU$. Hope that helps clarify what was meant in this old answer. – Gjergji Zaimi Aug 27 '18 at 15:59
• @MarkWildon I think I see the misunderstanding. When you have a word of length $n+k$ and have chosen $n-k$ marked white squares, the $2^{2k}$ denotes picking an arbitrary subset of colored vertices, not black vertices. Once you pick this subset, the values of the colored unmarked boxes will be uniquely determined. – Gjergji Zaimi Aug 27 '18 at 16:09
• @Gjergi Zaimi Yes, this was exactly my misunderstanding. Thank you. Your bijection is very nice! – Mark Wildon Aug 27 '18 at 16:19

Let us compute the ordinary generating function of $k \mapsto c_{n+k,k}$, i.e. $S(X) = \sum_{k \geq 0 } c_{n+k,k} X^k$ (with notations as in Lierre's answer above) : $$S(X^2) = \sum_j \sum_k \binom{2n + 2k + 1}{2j} \binom{n+k-j}{k-j} X^{2k}$$ $$= \sum_j \sum_l \binom{2n + 2l + 2j + 1}{2j} \binom{n+l}{l} X^{2l+2j}$$ $$=\frac{1}{2} \sum_l \binom{n+l}{l} X^{2l} \sum_{\varepsilon = \pm 1} \sum_j \binom{2n + 2l + j + 1}{j} (\varepsilon X)^{j}$$ $$=\frac{1}{2} \sum_{\varepsilon = \pm 1} \sum_l \binom{n+l}{l} \frac{X^{2l}}{(1-\varepsilon X)^{2n+2l+2}}$$ $$=\frac{1}{2} \sum_{\varepsilon = \pm 1} \frac{1}{(1-\varepsilon X)^{2n+2}(1-\frac{X^2}{(1-\varepsilon X)^2})^{n+1}}$$ $$=\frac{1}{2} \sum_{\varepsilon = \pm 1} \frac{1}{(1- 2\varepsilon X)^{n+1}} =\sum_k \binom{n+2k}{2k} 2^{2k} X^{2k}$$ hence the result.

This is certainly not the proof you wanted, but it does work.

Let $a_{j,k,n}$ the term you want to sum, and let $b_{k,n}$ the right hand side. I denote by $S_x$ the shift operator w.r.t. the variable $x$. For example $S_k \cdot a_{j,k,n} = a_{j,k+1,n}$.

You can check that $$\left((-1+k-n)S_n+(1+k+n)\right)\cdot a_{j,k,n} = (S_j-1)\cdot \left(\frac{-j+2 j^2}{-3+2 j-2 n} a_{j,k,n}\right)$$ and $$\left((1 + 3 k + 2 k^2)S_k + (2 k + 2 k^2 - 2 n - 2 n^2)\right)\cdot a_{j,k,n} = (S_j-1)\cdot \left( \frac{\left(-j+2 j^2\right) (k-n)}{-1+j-k} a_{j,k,n}\right).$$

What is interesting in these identities is that the right hand side is zero when you sum over $j$ from $0$ to $k$. More over, the operators on the left hand side does not contain $j$, so they commute with the summation w.r.t. $j$.

In the end, you obtain that the sum $c_{k,n} = \sum_{k=0}^n a_{j,k,n}$ satisfies the recurrence relations $$\left((-1+k-n)S_n+(1+k+n)\right)\cdot c_{k,n} = 0$$ and $$\left((1 + 3 k + 2 k^2)S_k + (2 k + 2 k^2 - 2 n - 2 n^2)\right)\cdot c_{k,n} = 0.$$

These recurrence relations are also satisfied by $b_{k,n}$ ! With a careful checking of some initial conditions, this is enough to prove the equality.

I did not compute by hand these so called telescoping relations, Mathematica did, with the package HolonomicFunctions.

CreativeTelescoping[Binomial[2 n + 1, 2 j]*Binomial[n - j, k - j], S[j] - 1, {S[k], S[n]}]`

Identity 1: let $F(n,j)=\frac{\binom{2n+1}{2j}\binom{n-j}{k-j}}{4^k\binom{n+k}{2k}}$ and $G(n,k)=-F(n,k)\frac{j(2j-1)}{(n+k+1)(2n-2j+3)}$.

Identity 2: let $F(n,j)=\frac{\binom{2n}{2j}\binom{n-j}{k-j}(n+k)}{4^kn\binom{n+k}{2k}}$ and $G(n,k)=-F(n,k)\frac{j(2j-1)}{(n+k)(2n-2j+1)}$.

Identity 3: let $F(n,j)=\frac{\binom{2n+1}{2j+1}\binom{n-j}{k-j}(n-k)}{4^k(2n+1)\binom{n+k}{2k+1}}$ and $G(n,k)=-F(n,k)\frac{j(2j-1)}{(n+k+1)(2n-2j+1)}$.

In all cases, $F(n+1,j)-F(n,j)=G(n,j+1)-G(n,j)$. Summing over all integers $j$, the RHS vanishes and hence $f(n):=\sum_jF(n,j)$ is constant. Check $f(0)=1$. The proofs follow.

This is called the Wilf-Zeilberger method.

Looking at (3.20) in Gould's tables, I have an idea of what might be his intended proof of the second identity. At the end of this answer I've indicated a bijective proof, using the same method as Gjergji Zaimi's answer. (This was a comment, but on rereading it, it didn't seem clear to me, so I'e expanded it below.)

It suffices to show that

$$\tag{\star}\sum_{j=0}^k \binom{2n}{2j} \binom{n-j}{k-j} = \frac{2^{2k}}{(2k)!}\prod_{j=0}^{k-1}(n^2-j^2)$$

since the right-hand side is easily seen to be $$\frac{2^{2k}}{2k}n\binom{n+k-1}{2k-1} = 2^{2k}\binom{n+k}{2k}\frac{n}{n+k}$$.

Let $$L(n)$$ denote the left-hand side and $$R(n)$$ denote the right-hand side in ($$\star$$). Each is a polynomial in $$n$$. Clearly $$L(n)$$ has roots for $$n \in \{0,1,\ldots, k-1\}$$. When $$n=k$$ we get $$\sum_{j=0}^k \binom{2k}{2j} = 2^{2k-1}$$. In all cases this agrees with $$R(n)$$. Evaluating $$L(n)$$ at $$n=-m$$ we get

$$\sum_{j=0}^k \binom{-2m}{2j} \binom{-m-j}{k-j} = \sum_{j=0}^k \binom{2j+2m-1}{2m-1} \binom{k+m-1}{k-j}(-1)^{k-j}$$

When $$m \ge 2$$ we can extend the sum so that the bottom limit is $$-(m-1)$$ since each binomial coefficient $$\binom{2j+2m-1}{2m-1}$$ vanishes for $$j \in \{-1,\ldots, -(m-1)\}$$. The right-hand side above is now the degree $$k+m-1$$ difference operator, $$\sum_{\ell=0}^{k+m-1} \binom{k+m-1}{\ell}(-1)^{\ell}$$ applies to the polynomial $$f(\ell) = \binom{2k + 2m - 1 - 2\ell}{2m-1}$$ of degree $$2m-1$$. Hence $$L(n)$$ has roots for $$n \in \{-1,\ldots,-(k-1)\}$$.

When $$m=k$$ the difference operator gives $$(2k-1)!$$ times the leading coefficient of $$f(-\ell)$$, namely $$2^{2k-1}/(2k-1)!$$. Therefore $$L(-k) = 2^{2k-1}$$; we saw above that $$R(k) = 2^{2k-1}$$, and clearly $$R$$ is even, therefore $$L(-k) = R(-k)$$.

This shows that $$L$$ and $$R$$ are polynomials in $$n$$ of degree $$2k$$ agreeing for all $$n \in \{-k,\ldots, k\}$$. Hence they are equal.

Remark. This proof could be significantly shortened if there was some easy reason why $$L(n)$$ is an even function of $$n$$. (As it is, this is only clear by the end of the proof.) In Gould's tables, $$L(n)$$ appears by expanding $$\cos 2nx = \Re (\cos x + \mathrm{i} \sin x)^{2n} = \sum_{j} \binom{2n}{2j} (-1)^{j} \sin^{2j}\!x (1-\sin^2\!x)^{n-j}$$ to get

$$\cos 2nx = \sum_{k=0}^n (-1)^k \sin^{2k}\!x \Bigl( \sum_{j=0}^k \binom{2n}{2j} \binom{n-j}{k-j} \Bigr).$$

If the right-hand side could somehow be defined for negative $$n$$, then the obvious evenness of $$\cos 2nx$$ would give the result. But I cannot see a way to make this formal argument correct.

Bijective proof. Start with $$2n$$ boxes in a row and choose $$2(n-j)$$ to colour white, black, $$\ldots$$, white, black. Then choose $$n-k$$ of the $$n-j$$ white boxes to mark. Next delete every box following a marked white box (the final box is either black or uncoloured, so this can be done), and the first box (which might be marked), and identify white and black. The resulting configuration has $$n+k-1$$ boxes, of which either $$n-k$$ or $$n-k+1$$ are white and marked, and some of the remaining boxes are coloured (with an unknown colour).

Given a configuration of the first type, insert a new box after each marked (white) box, and a new first box. The colours can then be reconstructed, as in Zaimi's proof, by working from right to left: if one has just coloured a box white (resp. black), and the next box to the left is marked, then the inserted box must be coloured black (resp. uncoloured). For the second type, insert a new box after each marked box, and two boxes at the start, the first of which is marked white, and then reconstruct the colours as before.

Hence

$$\sum_{j=0}^n \binom{2n}{2(n-j)}\binom{n-j}{k-j} = 2^{2k-1}\binom{n+k-1}{n-k} + 2^{2k}\binom{n+k-1}{n-k+1}$$

The right-hand side simplifies to

$$2^{2k}\binom{n+k}{n-k} \Bigl( \frac{k}{n+k} + \frac{n-k}{n+k} \Bigr) = 2^{2k} \binom{n+k}{2k} \frac{n}{n+k}$$

as required. The third identity can be proved very similarly.

In terms of hypergeometric series, the sum is $$\binom nk {}_2F_1(-n-1/2, -k; 1/2;1)$$, so the identity is a case of the Chu-Vandermonde theorem. It may be obtained from the more "usual-looking" case of Vandermonde's theorem $$\sum_j \binom{k-1/2}{k-j}\binom {n+1/2}{j} = \binom{n+k}{k}$$ by multiplying both sides by $$\binom nk/\binom{k-1/2}{k}$$ and simplifying.

Similarly, the other two identities are also cases of Vandermonde's theorem. The sums are $$\binom nk {}_2F_1(-n+1/2, -k; 1/2;1)$$ and $$(2n+1)\binom nk {}_2F_1(-n+1/2, -k; 3/2;1)$$

Incidentally, there is a fourth identity to go along with these three: $$\sum_{j=0}^k \binom{2n+2}{2j+1}\binom{n-j}{k-j} = 2^{2k+1}\binom{n+k+1}{2k+1}.$$ All four are equivalent to cases of Vandermonde's theorem.