Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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]}]