MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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, 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.

share|cite|improve this question
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.

share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.