Sum of squares of binomial coefficients

[J�r�me Collet]

Resent-From: <be...@illinois.edu>
From: J�r�me Collet <Jerome...@laposte.net>
Subject: Sum of squares of binomial coefficients
Date: October 11, 2012 10:37:25 AM MDT
To: "sci-math...@moderators.isc.org"
<sci-math...@moderators.isc.org>

I need to compute the sum :
\sum_{r,s}{ (\binom{r+s}{r} \binom{2m-r-s}{m-r})^2 �}
I know, because I used Stirling formula, Taylor-polynomials, and
ignored some problems on the borders, that this sum should be close to
\sqrt{2\pi m}.
The convergence is very fast, error is less than .5% if m>7.
Nevertheless, I do not know how to prove it correctly.

I am sure that two features of the problem are difficult : we have 2
indexes, and the summand is squared.

I read "A=B", from Zeilgerger, Petkovsek and Wilf, and tried to use the
Maxima tools developed to implement these ideas.
The result was very complicated, and I think useless. The Maxima input
is at the end of my post.
I think the cause is I try to compute a sum on 2 indexes. If I compute
a partial sum (on a column or a row, or even on a diagonal), the
recurrence is necessarily more complicated.
Do you think using multivariate versions of these methods (using Maple
or Mathematica) would help ?

The Maxima input :
To sum on lines:
load(zeilberger);
f:(binomial(r+s,r)*binomial(2*m-r-s,m-r))^2;
Zeilberger(f, r, s);

To sum on diagonals (r-s=2u or r+s=2t)
load(zeilberger);
f:(binomial(2*t,t+u)*binomial(2*m-2*t,m-t-u))^2;
Zeilberger(f, u, t);
Zeilberger(f, t, u);


Thanks for your help.

[Gavin Wraith]

In message <111020121212107442%ed...@math.ohio-state.edu.invalid>

���������J�r�me Collet <Jerome...@laposte.net> wrote:

> I need to compute the sum :
> \sum_{r,s}{ (\binom{r+s}{r} \binom{2m-r-s}{m-r})^2 �}
> I know, because I used Stirling formula, Taylor-polynomials, and
> ignored some problems on the borders, that this sum should be close to
> \sqrt{2\pi m}.
> The convergence is very fast, error is less than .5% if m>7.
> Nevertheless, I do not know how to prove it correctly.

This statement worries me. The expression you give
��\sum_{r,s}{ (\binom{r+s}{r} \binom{2m-r-s}{m-r})^2 �}
is certainly larger than
��\sum_{r,s}{ (\binom{r+s}{r} \binom{2m-r-s}{m-r}) �}
which evaluates to \binom{2m}{m}, unless I am mistaken.
And that grows much faster than \sqrt{2\pi m}.

--
Gavin Wraith (ga...@wra1th.plus.com)
Home page: http://www.wra1th.plus.com/

[Gavin Wraith]

In message <111020121555505579%ed...@math.ohio-state.edu.invalid>

Erratum: the penultimate line should read

"which evaluates to 4^m\binom{2m}{m}, unless I am mistaken."

This is the number of ways of choosing from a 2m-element set
an m-element subset and, independently a subset, call it A,
of any size. If we suppose that A has r+s elements, r of which
are in the m-element set, you can see why.
In any case, the expression given by Jerome has to exceed this
number but be less than its square.

[J�r�me Collet]

Le 11/10/2012 23:55, Gavin Wraith a �crit :

> In message <111020121212107442%ed...@math.ohio-state.edu.invalid>
> ��������J�r�me Collet <Jerome...@laposte.net> wrote:
> >
> > I need to compute the sum : \sum_{r,s}{ (\binom{r+s}{r}
> > \binom{2m-r-s}{m-r})^2 �} I know, because I used Stirling formula,
> > Taylor-polynomials, and ignored some problems on the borders, that
> > this sum should be close to \sqrt{2\pi m}. The convergence is very
> > fast, error is less than .5% if m>7. Nevertheless, I do not know
> > how to prove it correctly.
>
> This statement worries me. The expression you give ��\sum_{r,s}{
> (\binom{r+s}{r} \binom{2m-r-s}{m-r})^2 �} is certainly larger than
> ��\sum_{r,s}{ (\binom{r+s}{r} \binom{2m-r-s}{m-r}) �} which evaluates
> to \binom{2m}{m}, unless I am mistaken. And that grows much faster
> than \sqrt{2\pi m}.

I made a stupid mistake, I forgot a normalizing term, which is
\binom{2m}{m}^2
Thank for your attention.

So my question is

\sum_{r,s}{ (\binom{r+s}{r} \binom{2m-r-s}{m-r})^2 �}

seems to be equivalent to
\sqrt{2\pi m} \binom{2m}{m}^2
How can I prove it ?

[Gavin Wraith]

In message <121020120727017676%ed...@math.ohio-state.edu.invalid>

锟斤拷锟斤拷锟斤拷锟斤拷锟絁锟絩锟絤e Collet <Jerome...@laposte.net> wrote:

> So my question is

> \sum_{r,s}{ (\binom{r+s}{r} \binom{2m-r-s}{m-r})^2 锟絵

> seems to be equivalent to
> \sqrt{2\pi m} \binom{2m}{m}^2
> How can I prove it ?

A bit more attention; maybe not very useful. Suppose you have
a 2m-element set. Call a quadruple of subsets (A,B,U,V) such that
1) #U = #V = m
2) #A = #B
3) #(A\cap U) = #(B\cap V)
"jolly". Then I believe that
\sum_{r,s}{ (\binom{r+s}{r} \binom{2m-r-s}{m-r})^2 锟絵
is the number of jolly quadruples. Now \binom{2m}{m}^2 is
the number of ways of choosing pairs of subsets (U,V) such that
#U = #V = m. I am sceptical that all the rest of the jollity
counts asymptotically for \sqrt{2\pi m}. I would have expected something
a lot bigger, but I cannot give you any good reasons right now.

[Jérôme Collet]

I stated, by trial and errors that:
\sum_{r,s}{ (\binom{r+s}{r} \binom{2m-r-s}{m-r})^2 } = \binom{4m+1}{2m}
It is true for m from 1 to 250, with infinite precision calculations, so
I think it is true for all m.

But it is not a proof.
I will try do do it using manually Sister Celine's method, but if anyone
has a combinatorial proof, I am interested.

Le 13/10/2012 00:13, Gavin Wraith a écrit :
> In message <121020120727017676%ed...@math.ohio-state.edu.invalid>

> Jérôme Collet <Jerome...@laposte.net> wrote:
>
>> So my question is
>> \sum_{r,s}{ (\binom{r+s}{r} \binom{2m-r-s}{m-r})^2 }

>> seems to be equivalent to
>> \sqrt{2\pi m} \binom{2m}{m}^2
>> How can I prove it ?
>
> A bit more attention; maybe not very useful. Suppose you have
> a 2m-element set. Call a quadruple of subsets (A,B,U,V) such that
> 1) #U = #V = m
> 2) #A = #B
> 3) #(A\cap U) = #(B\cap V)
> "jolly". Then I believe that
> \sum_{r,s}{ (\binom{r+s}{r} \binom{2m-r-s}{m-r})^2 }