Prueba combinatoria de la suma de $\sum\limits_{k = 0}^n {n \choose k}^2= {2n \choose n}$

Question

Esperaba encontrar una prueba más "matemática", en lugar de probar lógicamente $\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$ .

Ya conozco la prueba lógica:

$${n \choose k}^2 = {n \choose k}{ n \choose n-k}$$

Por tanto, la suma puede expresarse como

$$\binom{n}{0}\binom{n}{n} + \binom{n}{1}\binom{n}{n-1} + \cdots + \binom{n}{n}\binom{n}{0}$$

Se puede pensar en ello como la elección de $n$ personas de un grupo de $2n$ (imagina dividir un grupo de $2n$ en $2$ grupos de $n$ personas cada uno. Puedo conseguir $k$ personas del grupo $1$ y otro $n-k$ personas del grupo $2$ . Lo hacemos desde $k = 0$ a $n$ .

Answer 1

Considerando que el producto de polinomios se puede expresar de la siguiente forma $$\sum_{l=0}^{2n}(\sum_{k=0}^{l}(b_{k})(a_{l-k}))x^l=(a_0+a_1x+...+a_nx^n)(b_0+b_1x+...+b_nx^n)$$

En particular $$\sum_{l=0}^{2n}(\sum_{k=0}^{l}\binom{n}{k}\binom{n}{l-k})x^l=(1+x)^{n}(1+x)^{n}=(1+x)^{2n}=\sum_{l=0}^{2n} \binom{2n}{l}x^l$$

$$\sum_{l=0}^{2n}(\sum_{k=0}^{l} \binom{n}{k}\binom{n}{l-k})x^l=\sum_{l=0}^{2n} \binom{2n}{l}x^l$$

Para cualquier l se tiene que

$$(\sum_{k=0}^{l} \binom{n}{k}\binom{n}{l-k})x^l=\binom{2n}{l}x^l$$

En particular para l = n

$$\sum_{k=0}^{n} \binom{n}{k}\binom{n}{n-k}=\binom{2n}{n}$$

$$\sum_{k=0}^{n} \binom{n}{k}\binom{n}{k}=\binom{2n}{n}$$

$$\sum_{k=0}^{n} \binom{n}{k}^2=\binom{2n}{n}$$

Q.E.D

Answer 2

Por doble cuenta Imagina que quieres hacer equipos con n personas y tienes n chicos y n chicas puedes hacer esto eligiendo n personas entre 2n personas que es $2n \choose n$ pero otra forma de contar esto es eligiendo cuántos chicos quieres en cada paso por ejemplo si quieres tener 3 chicos, entonces hay ${n \choose 3}*{n \choose n-3}={n \choose 3}^2$ formas de hacerlo, piénsalo un poco puedes elegir de 0 a n chicos en tu equipon entonces el número de equipos con n personas es $\sum_{k = 0}^n {n \choose k}^2$

Answer 3

Imagina que estamos distribuyendo $n$ caramelos indistintos a $k$ niños distinguibles. Por una aplicación directa de Bolas y Urnas, hay $${n+k-1\choose k-1}$$ formas de hacerlo. Como alternativa, podemos dar primero $0\le i\le n$ caramelos al niño mayor, de modo que esencialmente estamos dando $n-i$ caramelos a $k-1$ niños y de nuevo, con Bolas y Urnas, $${n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}$$ , lo que simplifica el resultado deseado.