Asymptotics de la suma de los cuadrados de los coeficientes binomiales

Question

Estamos tratando de estimar la cardinalidad $K(n,p)$ de los llamados Kuratowski monoid con $p$ positiva y $n$ negativo linealmente ordenado idempotente generadores. En particular, nos son de interés en el caso de $n=p$.

Esta idea surgió en una intersección de general de la topología y álgebra abstracta. Se calculó el valor exacto de

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

Tratamos de simplificar esta fórmula, sino que nos limitamos. El problema es que hay muchos tipos de binomio sumas son conocidos, pero no lo recuerdo entre ellos sumas de binomio "polinomios" de grado mayor que 1, que contiene la suma del índice anterior.

Si la suma diapason era un triángulo $\{i,j\ge 0:i+j\le 2n\}$ en lugar de un rectángulo $[0;n]\times [0;p]$, una suma que debe ser simplificada como sigue:

$$\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.$$

Un áspero asintótica de $K(n,n)$ debe $\log K(n,n)\sim n\log n+O(\log n)$, que sigue a la forma de los límites:

$$\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.$$

Ya que estamos topologists, es complicado para nosotros, para obtener un muy estimado asintótica, así que decidimos preguntar a los especialistas acerca de que.

Answer 1

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

Este teorema es una consecuencia de los siguientes resultados.

---

Para todos los enteros $0\le a,b\le n$ puesto $c_{a,b}(n)=\binom {2n-a-b}{n-a}/\binom {2n}n$.

Lema 1. Para todos los enteros $a,b\ge 0$ existe un límite de $\lim_{n\to\infty} c_{a,b}(n)=2^{-(a+b)}$.

Prueba. Se sigue de la igualdad de $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$

Para cada $n\ge 0$ puesto $k(n)=K(n,n)/\binom {2n}n^2$. Claramente que $k(n)= \sum_{a,b=0}^n c_{a,b}(n)^2$. The computer calculations suggest that the sequence $\{k(n):n\ge 3\}$ es cada vez mayor.

Proposición 1. Para cada una de las $n$ tenemos $k(n)\le 16/9$.

Prueba. $k(0)=1$, $k(1)=k(2)=7/4<16/9$, $k(3)=697/400<7/4$, y $k(4)=8549/4900<16/9$. Supongamos ahora que $n\ge 5$$k(n-1)\le 16/9$.

Vamos a utilizar los siguientes dos lemas.

Lema 2. Para cada una de las $a\le n$ tenemos $c_{a,0}(n)\le 2^{-a}$.

Prueba de ello Se sigue de la igualdad de $c_{a,0}(n)=\frac {n(n-1)\cdots (n-a+1)}{2n(2n-1)\cdots (2n-a+1)}$ y la desigualdad $(2n-l)\ge 2(n-l)$.$\square$

Lema 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)$.

Prueba. $c_{1,1}=\frac n{2(2n-1)}$, $c_{1,0}=1/2$, $c_{2,0}=\frac {n-1}{2(2n-1)}$, y $c_{3,0}=\frac {n-2}{4(2n-1)}$. La rutina de las transformaciones de la desigualdad de rendimiento $211\le 52n$, el cual tiene por $n\ge 5$.$\square$

Ahora tenemos que $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$

Proposición 2 existe un límite de $\lim_{n\to\infty} k(n)=16/9$.

Prueba. Lema 1 implica que $\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$. Por La Proposición 1, $\lim_{n\to\infty} k(n)=16/9$.$\square$

Answer 2

El argumento que usted ha escrito muestra que

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

La fórmula de Stirling da la asintótica

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

así que esta suma se comporta aproximadamente como una serie geométrica, y esperamos que

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

También tenemos el (fácilmente mejorado) límite inferior

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

y la fórmula de Stirling aquí da

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

así que nos ponemos los límites superior e inferior que se encuentran dentro de un factor multiplicativo de a $O(\sqrt{n})$ de cada uno de los otros de esta manera. Usted puede apretar el límite inferior mediante el refinado de entropía de la fórmula.