Prueba de una identidad combinatoria: $\sum_{i=0}^n {2i \choose i}{2(n-i)\choose n-i} = 4^n$

Question

Posible duplicado:
Identidad de los coeficientes binomiales

Esto era parte de una tarea que tenía, y no pude resolverlo. Ahora me está molestando. ¿Puede alguien ayudarme? Aunque una prueba estaría bien, no me importaría un empujón en la dirección correcta.

$\displaystyle\sum_{i=0}^n {2i \choose i}{2(n-i)\choose n-i} = 4^n$

Answer 1

Añadido: Por fin he corregido la prueba del lema crucial.

He aquí un argumento puramente combinatorio.

Dejemos que $\Sigma_{2n}$ sea el conjunto de cadenas binarias (cadenas de $0$ y $1$ ') de longitud $2n$ . Llamar a una cadena binaria equilibrado si contiene el mismo número de $0$ y $1$ 's. Sea $\Sigma_{2n}^B$ sea el conjunto de miembros equilibrados de $\Sigma_{2n}$ y que $\Sigma_{2n}^U$ sea el conjunto de cadenas desequilibradas en $\Sigma_{2n}$ que no tienen un segmento inicial equilibrado; los llamaré completamente desequilibrada . Claramente $\left|\Sigma_{2n}^B\right|=\binom{2n}n$ .

Para $\sigma=\langle b_1,\dots,b_{2n}\rangle\in\Sigma_{2n}$ y $1\le i\le k\le 2n$ dejar $\sigma(i,k)=\langle b_i,\dots,b_k\rangle$ y que $e_\sigma(i,k)$ sea el exceso de $1$ de más de $0$ 's en $\sigma(i,k)$ . Sea $\sigma^R(i,k)=\langle b_k,\dots,b_i\rangle$ La inversión de $\sigma(i,k)$ . Por último, dejemos que $\bar\sigma(i,k)=\langle \bar b_i,\dots,\bar b_k\rangle$ , donde $\bar b=1-b$ para $b\in\{0,1\}$ . Tenga en cuenta que $e_{\bar\sigma}(i,k)=-e_\sigma(i,k)$ .

Lema: $\left|\Sigma_{2n}^U\right|=\left|\Sigma_{2n}^B\right|$ .

Prueba corregida: Construiré una biyección $\Sigma_{2n}^B\to\Sigma_{2n}^U:\sigma\mapsto\hat\sigma$ .

Fijar $\sigma=\langle b_1,\dots,b_{2n}\rangle\in\Sigma_{2n}^B$ . Sea $m=\min\{e_\sigma(1,k):k=1,\dots,2n\}\le 0$ . Si $m=0$ , dejemos que $\tau=\sigma$ . De lo contrario, deja que $h$ sea el menor índice tal que $e_\sigma(1,h)=m$ . Sea $\tau=\sigma(h+1,2n)\bar\sigma^R(1,h)$ . Es decir, $\tau$ se obtiene de $\sigma$ transfiriendo el primer $h$ bits hasta el final, invirtiendo su orden y complementándolos en el proceso. Ahora $e_\sigma(1,2n)=0$ Así que $e_\sigma(h+1,2n)=-m$ y $$e_\tau(1,2n)=e_\sigma(h+1,2n)-e_\sigma(1,h)=-2m>0\;.$$ La elección de $h$ garantiza que $e_\tau(1,k)=e_\sigma(h+1,h+k)\ge 0$ para $k=1,\dots,2n$ . Si $e_\tau(1,k)>0$ para $k=1,\dots,2n$ , dejemos que $\hat\sigma=\tau\in\Sigma_{2n}^U$ .

En caso contrario, deja que $j$ sea mínima, tal que $e_\tau(1,j)=0$ . Si $\tau=\langle c_1,\dots,c_{2n}\rangle$ entonces claramente $c_j=0$ . Sea $$\tau'=\langle c_1,\dots,c_{j-1},1,c_{j+1},\dots,c_{2n}\rangle\;;$$ entonces $e_{\tau'}(1,k)>0$ para $k=1,\dots,2n$ . Por último, dejemos que $\hat\sigma=\overline{\tau'}$ ; $e_{\hat\sigma}(1,k)<0$ para $k=1,\dots,2n$ Así que $\hat\tau\in\Sigma_{2n}^U$ .

Ahora arreglar $\sigma=\langle b_1,\dots,b_{2n}\rangle\in\Sigma_{2n}^U$ . Supongamos primero que $e_\sigma(1,k)>0$ para $k=1,\dots,2n$ . Tenga en cuenta que $e_\sigma(1,2n)$ es par, y que $m=\frac12e_\sigma(1,2n)$ . Sea $h$ sea el mayor índice tal que $e_\sigma(1,h)=m$ y que $\tau=\bar\sigma^R(h+1,2n)\sigma(1,h)$ . La elección de $h$ garantiza que $e_\sigma(h+1,2n)=m$ y que $e_\sigma(h+1,k)>0$ para $k=h+1,\dots,2n$ Así que $e_\tau(1,2n-h)=-m$ y $e_\tau(k,2n-h)>-m$ para $k=1,\dots,2n-h$ . Además, $e_\sigma(1,k)>0$ para $k=1,\dots,h$ Así que $e_\tau(1,h)=-m$ es el mínimo de $e_\tau(1,k)$ para $k=1,\dots,2n$ y por lo tanto $\sigma=\hat\tau$ .

Supongamos ahora que $e_\sigma(1,k)<0$ para $k=1,\dots,2n$ claramente $e_{\bar\sigma}(1,k)>0$ para $k=1,\dots,2n$ . Sea $j$ sea el índice máximo tal que $\bar b_j=1$ y $e_{\bar\sigma}(1,j)=2$ . Sea $\sigma'$ se obtenga de $\bar\sigma$ sustituyendo $\bar b_j$ por $0$ . Entonces $e_{\sigma'}(1,k)>0$ para $k=1,\dots,j-1$ , $e_{\sigma'}(1,j)=0$ y $e_{\sigma'}(1,k)\ge 0$ para $k=j,\dots,2n$ . Si $e_{\sigma'}(1,2n)=0$ , dejemos que $\tau=\sigma'\in\Sigma_{2n}^B$ y observa que $\sigma=\hat\tau$ . De lo contrario, deja que $m=\frac12e_{\sigma'}(1,2n)$ y proceder como en el párrafo anterior: tomar $h$ para ser el mayor índice tal que $e_{\sigma'}(1,h)=m$ y que $\tau=\overline{\sigma'}^R(h+1,2n)\sigma'(1,h)$ . Como antes, $\sigma=\hat\tau$ . El mapa $\sigma\mapsto\hat\sigma$ es por tanto una biyección. $\dashv$

Para $\sigma = \langle b_1,\dots,b_{2n}\rangle\in\Sigma_{2n}$ dejar $m(\sigma)$ sea el mayor $k$ tal que $\langle b_1,\dots,b_{2k}\rangle$ está equilibrada, si tal $k$ existe; si no, que $m(\sigma)=0$ . Para $k=1,\dots,2n$ dejar $\Sigma_{2n}(k) = \{\sigma\in\Sigma_{2n}:m(\sigma)=k\}$ . Entonces $\sigma\in\Sigma_{2n}$ pertenece a $\Sigma_{2n}(k)$ si $\langle b_1,\dots,b_{2k}\rangle$ está equilibrado, y $\langle b_{2k+1},\dots,b_{2n}\rangle$ está completamente desequilibrada. Hay $\binom{2k}k$ cadenas equilibradas de longitud $2k$ y por el lema hay $\binom{2(n-k)}{n-k}$ cadenas completamente desequilibradas de longitud $2n-2k$ Así que $$\left|\Sigma_{2n}(k)\right|=\binom{2k}{k}\binom{2(n-k)}{n-k}.$$ Claramente $\Sigma_{2n} = \bigcup\limits_{k=0}^n\Sigma_{2n}(k)$ donde los conjuntos $\Sigma_{2n}(k)$ son disjuntos entre sí, por lo que $$\left|\Sigma_{2n}\right| = \sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}.$$ Pero por supuesto $|\Sigma_{2n}(k)| = 2^{2n} = 4^n$ Así tenemos el resultado deseado: $$\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=4^n.$$

Answer 2

Tenga en cuenta que se trata de un autoconvolución (la convolución de una secuencia consigo misma) de $\binom{2k}{k}$ . Podemos determinar que la función generadora de $\binom{2k}{k}$ es

$$\sum_{k=0}^\infty \binom{2k}{k} x^k=\frac1{\sqrt{1-4x}}$$

La función generadora de la autoconvolución se obtiene entonces elevando al cuadrado la función generadora original. Así, hay que determinar los coeficientes de la función $\dfrac1{1-4x}$ ...que puede ser refundido como una serie geométrica...

Answer 3

Mira Nota de Doron Zeilberger .