Asymptotics of the sum of squares of binomial coefficients

Question

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.

Answer 1

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.

Answer 2

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$