# Combinatorial identities

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?

• See also mathoverflow.net/questions/78870/…. – Dietrich Burde Nov 27 '13 at 9:31
• By rearranging the left hand side it can be transformed into the left hand side of the following identity without alternation: mathoverflow.net/questions/149574/… (With parameters $u=v=n \, , \, d=2n+1$). But computational evidence suggests that for general $u,v,d$ there is no nice formula for it (it has a ridiculously large prime factor for u=13,v=12,d=26). How did you come up with this identity? – Daniel Soltész Nov 27 '13 at 14:14
• Well computational evidence suggests that the formula from my previous comment tends to have ridiculously large prime factors for some $u=k \, , \, v=k+1 \, , \, d=u+v+1$. I got seriously distracted by this. – Daniel Soltész Nov 27 '13 at 14:27
• It is just a point of view. Suppose we want to construct binary words with length $4n+1$ that one half of these words has weight $n$ and the total weight of these words are greater or equal than $n$. Also, we need the half of these words with this property. This number can be obtained with the left hand side. For the right hand side, we choose $k$ positions from $4n+1$ positions and then from the last selected position (that is 1), we move $n+1$ positions forward (one way for obtaining a word by one half weight greater than $n$) and then choose $n-k$ positions among $3n-k$ remaining positions. – Shahrooz Janbaz Nov 27 '13 at 16:47

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.

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

• Very nice proof! – Ira Gessel Nov 27 '13 at 21:15
• I just came back again for one up vote to this nice answer. – Shahrooz Janbaz Nov 27 '13 at 22:11
• Thanks! I should have mentioned that the identity I used is (1.40) in Gould's tables: math.wvu.edu/~gould/Vol.4.PDF. The identity is equivalent to your form of Kummer's theorem (put $x=2a+1$), and in fact the proof also carries over (evaluate at $a=0,1,\ldots,n$). – Mark Wildon Nov 27 '13 at 22:18

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

• Thanks for your prompt reply. Anyway, I am looking for a proof of that, without computer – Marbor Nov 27 '13 at 11:15
• @Marbor: actually an interesting point you raise. You are probably looking for a "sequence of digestible steps" --- because otherwise this proof is also a proof .... – Suvrit Nov 27 '13 at 16:29