# Proof for a combinatorial identity

I have the following formula, which I believe it's true since it works in Mathematica for all values of $$N$$ I have tried, but I don't know how to prove it:

$$\sum_{q=0}^{N} {N \choose q}^2 x^{q} = \frac{1}{{2N \choose N}} \sum_{k,l=0}^N \; \sum_{s=0}^{\min(m, \ N-M)} \; \sum_{t=0}^{\min(m, \, N-M)} \\ {N \choose M} {M \choose m-s} {N-M \choose s} {N \choose N-m} {N-m \choose N-M-t} {m \choose t} x^{M-m+s+t}$$

where $$m=\min(k,l)$$ and $$M=\max(k,l)$$, and $$x$$ can be any complex number. I know one can write the LHS as a Legendre polynomial $$\sum_{q=0}^N { N \choose q }^2 x^q = (1-x)^N P_N \left( \frac{1+x}{1-x} \right)$$, and as a Hypergeometric function $$\sum_{q=0}^N { N \choose q }^2 x^q = \, _2F_1 (-N, -N, 1, x)$$, but apart from that I don't know how to simplify the RHS. I have tried Egorichev method to transform sums involving binomial coefficients into residual integrals, but didn't get much from there. Any ideas?

Edit: I have found yet another way of writing the same quantity:

$$\sum_{q=0}^{N} {N \choose q}^2 x^{q} = \\ = \frac{1}{ {2N \choose N} } \sum_{p,q=0}^N \, \sum_{r=\max(0, \, q+p-N)}^{\min (q, \, p)} \, \sum_{s=\max (0, \, q-p)}^{\min (q, \, N-p)} {N \choose p} {N \choose N-p} {p \choose r} {N-p \choose s} {N-p \choose q-r} {p \choose q-s} x^q$$

This one looks simpler than the previous one, since for instance here $$x$$ is decoupled from the sums in $$s$$ and $$t$$. Again I have tried Egorychev method on the RHS, which allows you to write the sums in $$s$$ and $$t$$ as complex contour integrals, and then you can easily choose your limits in the sum to be whatever is more convenient so that you can actually compute the sums in $$r$$ and $$s$$. But in exchange you now have four complex contour integrals (one for every summation limit you want to "kill"), so I don't know if this is simpler. I suspect there must be a more general identity relating all three expressions them. Any suggestions?

• If you set $x=a^{-1}bcd^{-1}$ you can reduce the clutter a bit. Commented Jul 16, 2020 at 15:01
• Yes thank you, edited Commented Jul 16, 2020 at 15:10
• If I haven't made any mistakes, the product of binomials can be written more symmetrically as $$\binom{N}{s,m-s,N-M-s,M-m+s}\binom{N}{t,m-t,N-M-t,M-m+t}$$ I don't know if that helps any. Commented Jul 16, 2020 at 16:18
• @MBolin I advocate two approaches, which might fail: (1) Induction on N. (2) Explore the problem's context. That is, where did this problem originate. If from a book or class, what theorems led up to this problem? Metacheating [as part of (2)], why was the problem presented at this point in the book or class? Commented Jul 17, 2020 at 12:53
• @user2661923 This is not from a book or class. I am working on a problem and these combinatorics appeared. Actually what I got is a more complicated formula, but for a particular case it simplifies to the two expressions I wrote above on the RHSs, and which can also be computed using the LHS. If I find a general identity to prove this, I will probably have a clue about how to simplify the more complicated formula I have (and write it as a generalization of the LHS). So I think induction on $N$ won't give me much insight into how these sums work... Commented Jul 17, 2020 at 13:36

Consider the coefficient of $$x^q$$ (and being slightly lazy with the limits of the sums) ... It suffices to show $$\begin{eqnarray*} \sum_{p,r,s} \binom{N}{p} \binom{N}{N-p} \binom{p}{r} \binom{N-p}{s} \binom{N-p}{q-r} \binom{p}{q-s} = \binom{2N}{N} \binom{N}{q}^2. \end{eqnarray*}$$ We shall use $$2$$ coeffiecient extractors $$\begin{eqnarray*} \binom{N-p}{s}= [x^0]: \frac{ (1+x)^{N-p} }{x^s} \\ \binom{N-p}{q-r} =[y^{0}]: \frac{(1+y)^{N-p}}{y^{q-r}}. \end{eqnarray*}$$ So $$\begin{eqnarray*} & &\sum_{p,r,s} \binom{N}{p} \binom{N}{N-p} \binom{p}{r} \binom{N-p}{s} \binom{N-p}{q-r} \binom{p}{q-s} \\ &=& \sum_{p} \binom{N}{p} \binom{N}{N-p} [x^0][y^{0}] : \sum_{r,s} \binom{p}{r} \binom{p}{q-s} \frac{ (1+x)^{N-p} }{x^s} \frac{(1+y)^{N-p}}{y^{q-r}} \\ &=& \sum_{p} \binom{N}{p} \binom{N}{N-p} [x^0][y^{0}] : \frac{ (1+x)^{N-p} (1+y)^{N-p}}{x^q y^q}\sum_{r} \binom{p}{r}y^r \binom{p}{q-s} x^{q-s} \\ &=& \sum_{p} \binom{N}{p} \binom{N}{N-p} [x^0][y^{0}] : \frac{ (1+x)^{N} (1+y)^{N}}{x^q y^q}\\ &=& \binom{N}{q}^2 \sum_{p} \binom{N}{p} \binom{N}{N-p}. \end{eqnarray*}$$ Now recall the well known plum $$\begin{eqnarray*} \sum_{p} \binom{N}{p} \binom{N}{N-p} = \binom{2N}{N} \end{eqnarray*}$$ and we are dumb. $$\ddot \smile$$

• Could you explain the second to last equality? (the one that eliminates the sum over $r$) Oh I guess I get it now (there is just a $\sum\limits_s$ missing) Commented Jul 25, 2020 at 9:59
• Yes, I think that is right. However I still don't know what to do with the first identity. Commented Jul 27, 2020 at 8:59

OK I think I have a partial answer that might help prove the second identity by definition. However, I still don't know how this would apply to the first identity. Moreover, I would still like to understand this in a more general way. Therefore I will leave the bounty open. I am only writing this answer to perhaps help someone else to give a full answer.

Basically the trick is the definition of the Hypergeometric function or, in general, the Generalized hypergeometric function. A sum

$$\phi = \sum_{n \geq 0} \beta_n z^n$$

is a Generalized hypergeometric function if the fraction $$\beta_{n+1}/\beta_n$$ is some rational function of $$n$$. In particular, the above sum is defined to be the Generalized hypergeometric function $$_pF_q (a_1, ..., a_p ; \, b_1, ..., b_q ; \, z)$$ if the sum coefficients satisfy (up to some overall factor that can be reabsorbed in $$z$$)

$$\frac{\beta_{n+1}}{\beta_n} = \frac{(a_1+n) ... (a_p+n)}{(b_1+n) ... (b_q + n)(1+n)}$$

where the $$a$$'s and $$b$$'s are just the roots of the polynomials on the numerator and the denominator respectively. One can check straightforwardly that the sum

$$\sum_{q=0}^N { N \choose q }^2 x^q$$

gives $$\frac{\beta_{q+1}}{\beta_q} = \frac{(-N+q)^2}{(1+q)^2}$$. Now for the second sum

$$\frac{1}{ {2N \choose N} } \sum_{p,q=0}^N \, \sum_{r=\max(0, \, q+p-N)}^{\min (q, \, p)} \, \sum_{s=\max (0, \, q-p)}^{\min (q, \, N-p)} {N \choose p} {N \choose N-p} {p \choose r} {N-p \choose s} {N-p \choose q-r} {p \choose q-s} x^q$$

I don't know exactly how one can compute it, but Mathematica does give me $$\frac{\beta_{q+1}}{\beta_q} = \frac{(-N+q)^2}{(1+q)^2}$$. So they are both equal to $$_2F_1(-N, -N; 1; x)$$.

I don't know how one can check this for the first sum since there the exponent of $$x$$ is not just $$q$$. Suggestions are welcome.