# Asymptotics of the sum of squares of binomial coefficients

We are trying to estimate the cardinality $K(n,p)$ of so-called Kuratowski monoid with $p$ positive and $n$ negative linearly ordered idempotent generators. In particular, we are interesting in the case $n=p$.

This notion arose in an intersection of general topology and abstract algebra. We calculated the exact value of

$$K(n,p)=\sum_{i=0}^n\sum_{j=0}^p \binom {i+j}i\binom{i+j}j.$$

We try to simplify this formula, but we stuck. The problem is that many different binomial sums are known, but I cannot remember among them sums of binomial “polynomials” of degree greater than 1, containing the summation index above.

If the summation diapason was a triangle $\{i,j\ge 0:i+j\le 2n\}$ instead of a rectangle $[0;n]\times [0;p]$, a sum should be simplified as follows:

$$\sum_{i,j=0}^{i+j\le 2n} \binom {i+j}i^2=\sum_{k=0}^{2n}\sum_{i,j=0}^{i+j=k}\binom ki^2=\sum_{k=0}^{2n}\binom {2k}k.$$

A rough asymptotic of $K(n,n)$ should be $\log K(n,n)\sim n\log n+O(\log n)$, which follows form the bounds:

$$\binom {2n}n^2\le K(n,n)= \sum_{i=0}^n\sum_{j=0}^p \binom {i+j}i\binom{i+j}j\le 2(n+1)^2\binom {2n}n^2.$$

Since we are topologists, it is complicated for us to obtain a highly estimated asymptotic, so we decided to ask specialists about that.

-
Just to be clear. You want the asymptotic of $$\sum_{i=0}^n\sum_{j=0}^n \binom {i+j}i\binom{i+j}j.$$ Right? –  user17762 Apr 24 '13 at 23:52
The bounds you've obtained already seem pretty good. You need tighter bounds? –  Qiaochu Yuan Apr 24 '13 at 23:56
@user17762 Yes, you are right. We are interested in asymptotics or simpler formulas for this sum. Also we consider the respective sum for $K(n,p)=\sum_{i=0}^n \sum_{i=0}^p \binom {i+j}i\binom{i+j}j$. –  Alex Ravsky Apr 25 '13 at 3:48
@QiaochuYuan I prefer a word “prefer” instead of “need”, :-) because our main results (the derivation of $K(n,p)$) are already publishable. But we decided that it would be nice to simplify its form (when I devised how to simplify the initial ($\sum \sum \sum \sum \sum \sum\dots$ to the present form, I was proposed to be a coauthor. :-) ) –  Alex Ravsky Apr 25 '13 at 5:29
@vadim123: Thank you for the interest to our investigation. My experience suggests a pessimistic attitude for the existence of a simple formula for $K(n,n)$. Moreover, the sequence $\{K(n,n)\}$ is not even in the On-Line Encyclopedia of Integer Sequences. –  Alex Ravsky Apr 28 '13 at 15:55

Theorem. $\lim_{n\to\infty} K(n,n)/\binom {2n}n^2=16/9$.

This theorem is a corollary of the following results.

For every integers $0\le a,b\le n$ put $c_{a,b}(n)=\binom {2n-a-b}{n-a}/\binom {2n}n$.

Lemma 1. For every integers $a,b\ge 0$ there exists a limit $\lim_{n\to\infty} c_{a,b}(n)=2^{-(a+b)}$.

Proof. It follows from the equality $c_{a,b}(n)=\frac {n(n-1)\cdots (n-a+1) n(n-1)\cdots (n-b+1)}{2n(2n-1)\cdots (2n-a-b+1)}.\square$

For every $n\ge 0$ put $k(n)=K(n,n)/\binom {2n}n^2$. Clearly that $k(n)= \sum_{a,b=0}^n c_{a,b}(n)^2$. The computer calculations suggest that the sequence $\{k(n):n\ge 3\}$ is increasing.

Proposition 1. For each $n$ we have $k(n)\le 16/9$.

Proof. $k(0)=1$, $k(1)=k(2)=7/4<16/9$, $k(3)=697/400<7/4$, and $k(4)=8549/4900<16/9$. Suppose now that $n\ge 5$ and $k(n-1)\le 16/9$.

We shall use the following two lemmas.

Lemma 2. For each $a\le n$ we have $c_{a,0}(n)\le 2^{-a}$.

Proof It follows from the equality $c_{a,0}(n)=\frac {n(n-1)\cdots (n-a+1)}{2n(2n-1)\cdots (2n-a+1)}$ and the inequality $(2n-l)\ge 2(n-l)$.$\square$

Lemma 3. $(16/9)c_{1,1}^2+2c_{1,0}^2+2c_{2,0}^2+2c_{3,0}^2\le (16/9)\cdot(1/16)+2(1/4)+2(1/16)+2(1/64)$.

Proof. $c_{1,1}=\frac n{2(2n-1)}$, $c_{1,0}=1/2$, $c_{2,0}=\frac {n-1}{2(2n-1)}$, and $c_{3,0}=\frac {n-2}{4(2n-1)}$. The routine transformations of the inequality yield $211\le 52n$, which holds for $n\ge 5$.$\square$

Now we have that $k(n,n)\le k(n-1)c_{1,1}^2+1+2\sum_{a=1}^{n-1} c_{a,0}^2\le (16/9)\cdot(1/16)+1+\sum_{a=1}^{n-1}2^{-2a}\le 16/9$.$\square$

Proposition 2 There exists a limit $\lim_{n\to\infty} k(n)=16/9$.

Proof. Lemma 1 implies that $\underline\lim_{n\to\infty} k(n)\ge \sum_{a,b=0}^\infty 2^{-2(a+b)}=\sum_{i=0}^\infty (i+1)4^{-i}=16/9$. By Proposition 1, $\lim_{n\to\infty} k(n)=16/9$.$\square$

-
(+1) Brilliant! –  userNaN May 4 '13 at 16:54

The argument you've written down shows that

$$K(n, n) \le \sum_{k=0}^{2n} {2k \choose k}.$$

Stirling's formula gives the asymptotic

$${2k \choose k} \sim \frac{4^k}{\sqrt{\pi k}}$$

so this sum behaves approximately like a geometric series, and we expect that

$$\sum_{k=0}^{2n} {2k \choose k} \sim \frac{4}{3} \left( \frac{4^{2n}}{ \sqrt{2 \pi n} } \right).$$

We also have the (easily improved) lower bound

$${2n \choose n}^2 \le K(n, n)$$

and Stirling's formula here gives

$${2n \choose n}^2 \sim \frac{4^{2n}}{\pi n}$$

so we get upper and lower bounds that are within a multiplicative factor of $O(\sqrt{n})$ of each other this way. You can tighten the lower bound using the refined entropy formula.

-
Thank for your answer. I’ will study the page which your linked and try to apply its ideas to our problem. –  Alex Ravsky Apr 25 '13 at 5:30
Asking my question, I tried to avoid long calculations, like evaluating the bounds for tails of “like”-geometric series or obtained from Refined entropy formula or similar limit theorems. I hoped that such approximations are already known, that there is a formula estimating already a sum (but some of the summands seems to be rapidly increasing with all the consequences of this fact). This is why I not tried to refine my initial rough bounds. –  Alex Ravsky Apr 25 '13 at 5:30
Concerning the refinement of a lower bound. I remark that now it is not clear for me how tight is the upper bound. When we derive the upper bound $\sum_{k=0}^{2n}\binom {2k}k,$ we add to the square domain of the summations two triangles with big summands. We may try to obtain a tighter upper bound from the following idea: –  Alex Ravsky Apr 25 '13 at 5:31
$$K(n,n)=\sum_{i=0}^n\sum_{j=0}^p \binom {i+j}i\binom{i+j}j \le$$ $$\sum_{k=0}^{n}\sum_{i,j=0}^{i+j=k}\binom ki^2+\sum_{k=n+1}^{2n}\binom k{\lfloor k/2\rfloor}^2(2n+1-k)\sim$$ $$\frac 43\frac {4^n}{\sqrt{\pi n}}+\sum_{k=n+1}^{2n} \frac {2^{2k+1}}{\pi k}(2n+1-k),$$ and the second summand is like a geometric series too. –  Alex Ravsky Apr 25 '13 at 12:50