Combinatorial identities

Question

I have computational evidence that $$\sum_{k=0}^n \binom{4n+1}{k} \cdot \binom{3n-k}{2n}= 2^{2n+1}\cdot \binom{2n-1}{n}$$ but I cannot prove it. I tried by induction, but it seems hard. Does anyone have an idea how to prove it? What about $$\sum_{k=0}^n \binom{4n+M}{k} \cdot \binom{3n-k}{2n}$$ where $M\in\mathbb{Z}$? Is there a similiar identity?

Answer 1

The first formula is a special case of one of the standard hypergeometric series summation formulas called Kummer's theorem. (See, e.g., http://mathworld.wolfram.com/KummersTheorem.html or http://en.wikipedia.org/wiki/Hypergeometric_function#Kummer.27s_theorem.)

The first formula may be written as $$\sum_{k=0}^n \binom{4n+1}{k} \binom{3n-k}{n-k} = 2^{2n} \binom{2n}{n}. $$ The general terminating form of Kummer's theorem may be written $$ \sum_{k=0}^n \binom{2a+1}{k}\binom{2a-n-k}{n-k} = 2^{2n}\binom an; $$ the OP's identity is the case $a=2n$.

I don't know of a really simple proof of this identity (i.e., as simple as many proofs of Vandermonde's theorem); but it can be derived by standard methods from other summation formulas, or by Lagrange inversion, or from formulas for powers of the Catalan number generating function, or by Zeilberger's algorithm or the WZ method.

For an exposition of the connection between binomial coefficient sums and hypergeometric series, see the third chapter of Petkovsek, Wilf, and Zeilberger's A=B.

For the second identity, for each fixed integer value of $M$, the sum, and more generally, $$ \sum_{k=0}^n \binom{2a+M}{k}\binom{2a-n-k}{n-k} $$ can be expressed as the sum of a fixed number (something like $|M|$) of nice terms (probably just binomial coefficients times powers of 2, though I haven't worked out the details). You can find more than you want to know about these identities in the paper

Raimundas Vidunas, A generalization of Kummer's identity, Rocky Mountain J. Math. Volume 32, Number 2 (2002), 919-936.

though you will have to do some work to convert his formulas to binomial coefficients.

Answer 2

Here is a proof repeating the trick I used in this earlier answer. By negating the second binomial coefficient, the identity in the question is equivalent to

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

This is the special case $x= 4n+1$ of the following identity

$$ \sum_{k=0}^n (-1)^k \binom{x}{k}\binom{2n-x}{n-k} = (-1)^n 2^{2n} \binom{(x-1)/2}{n}. $$

When $x=2r+1$ is odd the left-hand side is zero since the summands for $k=r-j$ and $k=r+1+j$ cancel. So the two sides agree when $x=1,3,\ldots,2n-1$. When $x = 2n+1$ the left-hand side is $\sum_{k=0}^n (-1)^n \binom{2n+1}{k} = (-1)^n 2^{2n+1}/2 = (-1)^n 2^{2n}\binom{n}{n}$. So the two sides agree at $n+1$ points. Since they are polynomials of degree $n$ in $x$, they must agree for all $x$.

Answer 3

According to sage your first sum is:

$$ \frac{8^{n} 2^{n} \left(n - \frac{1}{2}\right)!}{\sqrt{\pi} n!} $$

According to Maple your second sum is:

$${3\,n\choose 2\,n}{2F1(-n,-4\,n-M;\,-3\,n;\,-1)}-{4\,n+M\choose n+1}{ 2\,n-1\choose 2\,n}{3F2(1,1,-3\,n-M+1;\,n+2,-2\,n+1;\,-1)}$$

For $M=2$:
$$\frac{2 \, {\left(2 \, n \Gamma\left(\frac{3}{4}\right) \Gamma\left(\frac{1}{4}\right) + \Gamma\left(\frac{3}{4}\right) \Gamma\left(\frac{1}{4}\right)\right)} 8^{n} 2^{n} \left(n - \frac{1}{2}\right)!^{2} - \pi 4^{2 \, n + 1} \left(n + \frac{1}{4}\right)! \left(n - \frac{1}{4}\right)!}{\sqrt{\pi} \left(n + 1\right)! \left(n - \frac{1}{2}\right)! \Gamma\left(\frac{3}{4}\right) \Gamma\left(\frac{1}{4}\right)} $$

For $M=3$:
$$ \frac{2 \, {\left(2 \, {\left(6 \, n^{2} \Gamma\left(\frac{3}{4}\right) \Gamma\left(\frac{1}{4}\right) + 7 \, n \Gamma\left(\frac{3}{4}\right) \Gamma\left(\frac{1}{4}\right) + 2 \, \Gamma\left(\frac{3}{4}\right) \Gamma\left(\frac{1}{4}\right)\right)} 8^{n} 2^{n} \left(n - \frac{1}{2}\right)!^{2} - \pi 4^{2 \, n + 2} \left(n + \frac{3}{4}\right)! \left(n + \frac{1}{4}\right)!\right)}}{\sqrt{\pi} \left(n + 2\right)! \left(n - \frac{1}{2}\right)! \Gamma\left(\frac{3}{4}\right) \Gamma\left(\frac{1}{4}\right)} $$