Coeficientes del binomiales de la prueba: $\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$.

Question

Demostrar que $\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$.

Estoy tratando de demostrar mediante la inducción. Estoy teniendo algunos problemas después de la inducción de paso.

Aquí es lo que tengo hasta ahora:

Voy a empezar con ${2(m+1) \choose m+1}$ y quieres trabajar en mi camino a la suma, con m+1.

Utilizando la ley de Pascal dos veces, ${2(m+1) \choose m+1}$= ${2m \choose m-1}$+${2m \choose m}$+${2m \choose m}$+${2m \choose m+1}$= $\sum_{k=0}^m {m \choose k} ^{2}$ +$\sum_{k=0}^m {m \choose k} ^{2}$+${2m \choose m+1}$+${2m \choose m+1}$= 2[$\sum_{k=0}^m {m \choose k} ^{2}$+${2m \choose m+1}]$.

La segunda igualdad es por la hipótesis de inducción. No estoy seguro de qué hacer con el factor adicional de dos, y si hay cualquier teoremas acerca de los coeficientes binomiales que podría ayudar.

Gracias!

Answer 1

Combinatoria Prueba

Tener en cuenta el número de caminos en el entero entramado de $(0,0)$ $(n,n)$solo pasos de la forma: $$(i,j)→(i+1,j)$$ $$(i,j)→(i,j+1)$$

es decir, ya sea hacia la derecha o hacia arriba. Este proceso se lleva a $2n$ pasos, de los cuales, $n$ son pasos a la derecha. Así, el número total de rutas a través de la gráfica es igual a $\binom{2n}{n}$.

Ahora vamos a contar las rutas de acceso a través de la red por primera recuento de los caminos:

$\qquad$ (1) $(0,0)$ $(k,n−k)$

y, a continuación, las rutas de acceso:

$\qquad$(2): de$(k,n−k)$$(n,n)$.

Tenga en cuenta que cada uno de estos caminos es el de la longitud de la $n$.

Ya que cada ruta es $n$ pasos de largo, cada extremo de ser de la forma $(k,n−k)$ algunos $k\in\{1,2,\ldots,n\}$, representando $k$ pasos a la derecha y $n−k$ pasos.

Tenga en cuenta que el número de caminos a través de los $(k,n−k)$ es igual a $\binom{n}{k}$, ya que somos libres de elegir el $k$ pasos en cualquier orden. También puede contar el número de n-paso de las rutas desde el punto de $(k,n−k)$$(n,n)$. Estas rutas se compone de $n−k$ pasos a la derecha y $k$ pasos. Por lo tanto, el número de estas rutas es igual a $\binom{n}{n−k}=\binom{n}{k}$.

Así, el número total de rutas de $(0,0)$ $(n,n)$que pasan a través de $(k,n−k)$ es igual al producto del número de rutas posibles de $(0,0)$ $(k,n−k)$es decir $\binom{n}{k}$, y el número de rutas posibles de $(k,n−k)$ $(n,n)$i.e $\binom{n}{k}$.

Por lo que el número total de rutas a través de $(k,n−k)$ es igual a $\binom{n}{k}^2$.

Sumando sobre todos los posibles valores de $k=0,\ldots,n$ da el número total de rutas.

Así, tenemos: $$ \sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n} $$

Answer 2

Más simple para probar por inducción es Vandermonde de la Identidad: $$ \sum_{j=0}^k\binom{n}{j}\binom{m}{k-j}=\binom{n+m}{k}\etiqueta{1} $$ Para $n=0$, tenga en cuenta que el único no-cero término de la suma es al $j=0$. Por lo tanto, la suma es $$ \binom{m}{k}\etiqueta{2} $$ como $(1)$ dice. Ahora, suponga que $(1)$ mantiene para $n$, a continuación, calcular $$ \begin{align} \sum_{j=0}^k\binom{n+1}{j}\binom{m}{k-j} &=\sum_{j=0}^k\binom{n}{j}\binom{m}{k-j}+\sum_{j=0}^k\binom{n}{j-1}\binom{m}{k-j}\\ &=\sum_{j=0}^k\binom{n}{j}\binom{m}{k-j}+\sum_{j=0}^{k-1}\binom{n}{j}\binom{m}{k-1-j}\\ &=\binom{n+m}{k}+\binom{n+m}{k-1}\\ &=\binom{n+m+1}{k}\tag{3} \end{align} $$ Por lo tanto, $(1)$ mantiene para $n+1$.

La aplicación de $(1)$ a tu pregunta de los rendimientos $$ \begin{align} \sum_{k=0}^n\binom{n}{k}^2 &=\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}\\ &=\binom{2n}{n}\tag{4} \end{align} $$

Answer 3

Aquí está una prueba de conteo de dos maneras. Considere dos urnas, una con $n$ bolas de color rojo y otro que contenga $n$ bolas de color azul. El número total de formas de elegir los $n$ bolas (independientemente del color) en todos los de las dos urnas es ${2n \choose n}$. Alternativamente, $k$ bolas de color rojo puede ser elegido de la primera urna (en ${n \choose k}$ formas) y para cada una de las $k$, $n-k$ blues bolas puede luego ser recogido de la otra urna (en ${n \choose n-k}$ formas). Por lo tanto, el número total de maneras para recoger $n$ bolas que $k$ de ellos son de color rojo es ${n \choose k}{n \choose n-k} = {n \choose k}{n \choose k}$. Suma más de $k$, el número total de maneras en que se $\sum_{k=0}^{n}{n \choose k}^{2}$.

Answer 4

Vamos a ver qué pasa si tenemos en cuenta $$\begin{align*} \binom{n+1}{k}^{\!2} &= \left(\binom{n}{k-1} + \binom{n}{k}\right)^{\!2} \\ &= \binom{n}{k-1}^{\!2} + \binom{n}{k}^{\!2} + 2\binom{n}{k-1}\binom{n}{k}. \end{align*}$$ Now taking the sum from $k = 0$ to $n+el 1$, observing that $\binom{n}{n+1} = 0$ and $\binom{n}{-1} = 0$, we get $$\sum_{k=0}^{n+1} \binom{n+1}{k}^{\!2} = 2\sum_{k=0}^n \binom{n}{k}^{\!2} + 2\sum_{k=1}^{n} \binom{n}{k-1}\binom{n}{k}.$$ We now wish to show the second sum on the RHS is $\binom{2n}{n+1}$. But this is a special case of Vandermonde's convolution/identity $$\sum_x \binom{r}{a+x}\binom{s}{b-x} = \binom{r+s}{a+b}, \quad a, b \in \mathbb Z,$$ where $r = s = b = 1$ and $a = -1$. El resto sigue por inducción a partir de los cálculos previamente establecido.

Pero he aquí lo curioso: la identidad original, es en sí mismo un caso especial de Vandermonde, con la elección $r = s = n$, $x = k$, $a = 0$, $b = n$, desde $\binom{n}{n-k} = \binom{n}{k}$. He aquí otro método: Inductivo Prueba de Vandermonde de la Identidad?

Answer 5

Yo sé que usted quiere a una inducción de la prueba de ello, pero creo que no puede resistirse a darle una combinatoria. El lado derecho es la respuesta a la pregunta: "¿En cuántas formas puedo dibujar $n$ elemento de una $2n$ element set" - obviamente ${2n\choose n}$

Para obtener el lado derecho permite dividir nuestro $2n$ conjunto en dos n-elemento subconjuntos, y permite dibujar $k$ elementos de la primera y $n-k$ elementos de la segunda. Hay ${n\choose k}{n\choose n-k}={n\choose k}{n\choose k}={n\choose k}^2$ maneras de hacerlo. Podemos hacerlo para cada k desde 1 hasta n y la suma nos da el total de número de formas de elegir los n elementos de un conjunto de 2n, por lo tanto: $$\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$$