6
$\begingroup$

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?

$\endgroup$
7
  • 2
    $\begingroup$ If you set $x=a^{-1}bcd^{-1}$ you can reduce the clutter a bit. $\endgroup$ Commented Jul 16, 2020 at 15:01
  • 1
    $\begingroup$ Yes thank you, edited $\endgroup$
    – MBolin
    Commented Jul 16, 2020 at 15:10
  • 1
    $\begingroup$ 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. $\endgroup$
    – saulspatz
    Commented Jul 16, 2020 at 16:18
  • 1
    $\begingroup$ @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? $\endgroup$ Commented Jul 17, 2020 at 12:53
  • 1
    $\begingroup$ @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... $\endgroup$
    – MBolin
    Commented Jul 17, 2020 at 13:36

2 Answers 2

2
+50
$\begingroup$

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$

$\endgroup$
2
  • $\begingroup$ 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) $\endgroup$ Commented Jul 25, 2020 at 9:59
  • $\begingroup$ Yes, I think that is right. However I still don't know what to do with the first identity. $\endgroup$
    – MBolin
    Commented Jul 27, 2020 at 8:59
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .