Demostrar que $\sum_{k=0}^m \dbinom{n}{k} \dbinom{n-k}{m-k}= 2^m \dbinom{n}{m}$ $m < n $

Question

Demostrar que $\sum_{k=0}^m \dbinom{n}{k} \dbinom{n-k}{m-k}= 2^m \dbinom{n}{m}$ $m < n $

En resumen : he tratado de demostrar mediante la inducción, ya que no puede ver realmente cómo interpretar esto con un argumento combinatorio,a continuación me proporcionar mi forma de pensar

Inducción en $m$ me han demostrado el caso base $m=1$,ya que he

\begin{array} \space \dbinom{n}{0} \dbinom{n}{1} +\dbinom{n}{1} \dbinom{n-1}{0} & =2 \dbinom{n}{1} \\ n+n & =2n \\ \end{array}

Suponiendo que se mantenga por $m=j$ he $\sum_{k=0}^j \dbinom{n}{k} \dbinom{n-k}{j-k}= 2^j \dbinom{n}{j}$

(No escribo el reclamo por el bien de espacio y tiempo)

Así que para completar la inducción tengo que demostrar que

$$ 2^{j+1} \dbinom{n}{j+1} =2^j \dbinom{n}{j} +\dbinom{n}{k} \dbinom{n-k}{(j+1)-k}$$

que es más bien una bestia para simplificar...

Alguien puede ayudarme ?

(Cualquier prueba es bienvenido,aunque yo también agradecería si alguien me puede ayudar con la inducción de la prueba)

Answer 1

Usted tiene $$ \binom{n}{k} \binom{n-k}{m-k} = \frac{n!}{k!(m-k)!(n-m)!} = \binom{n}{m} \binom{m}{k}, $$ así $$ \sum_{k=0}^m \binom{n}{k} \binom{n-k}{m-k} = \binom{n}{m} \sum_{k=0}^m \binom{m}{k} = 2^m \binom{n}{m}. $$

PS: también Se puede interpretar esta fórmula combinatoricaly: El lado derecho $2^m \binom{n}{m}$ nos dice que tenemos $n$ incoloro, de bolas, de las cuales elegimos $m$ muchos (dándonos $\binom{n}{m}$), y la pintura de cada uno de ellos, ya sea negro o blanco (dándonos $2^m$). El plazo $\binom{n}{k} \binom{n-k}{m-k}$ en el lado izquierdo nos dice que elijamos $k$ bolas para pintura negra y, a continuación, $m-k$ bolas de pintura blanca; sumando esto a través de $k = 0, 1, \dotsc, m$ nos da el mismo resultado que antes.

Answer 2

Otra solución es por la doble contabilización.

Supongamos que tenemos n bolas, y queremos elegir m bolas entre ellos y el color de cada uno de ellos por el azul o el rojo. En cuántas formas podemos hacerlo?

Lado derecho: Se puede elegir simplemente m de n bolas ( $n \choose m$ ) y, a continuación, elija un color para cada uno de estos m bolas ($2^m$).

Lado izquierdo: podemos optar $k$ bolas a ser de color azul ( $n \choose k$ ) y la m-k bolas de las bolas restantes a ser de color rojo ( $n-k \choose m-k$ ) y debemos hacerlo para todos los $1\leq k \leq m$.

Answer 3

Sugerencia: La siguiente técnica también puede ser útil en las situaciones más complicadas.

Utilizamos el coeficiente de operador $[x^n]$ para denotar el coeficiente de $x^{n}$ en un polinomio o una serie $A(x)=\sum_{k=0}^{\infty}a_kx^k$. Podemos escribir por ejemplo \begin{align*} \binom{n}{k}=[x^k](1+x)^n \end{align*}

Obtenemos para $0\leq m\leq n$

\begin{align*} \sum_{k=0}^m&\binom{n}{k}\binom{n-k}{m-k}\\ &=\sum_{k=0}^\infty[x^k](1+x)^n[y^{m-k}](1+y)^{n-k}\tag{1}\\ &=[y^m](1+y)^n\sum_{k=0}^{\infty}y^k(1+y)^{-k}[x^k](1+x)^n\tag{2}\\ &=[y^m](1+y)^n\left(1+\frac{y}{1+y}\right)^n\tag{3}\\ &=[y^m](1+2y)^n\\ &=\binom{n}{m}2^m \end{align*}

Comentario:

• En (1) utilizamos el coeficiente de operador dos veces y establecer el límite superior de la suma a $\infty$ sin cambiar nada, ya que sólo agregar cero.

• En (2) nos reorganizar la suma mediante el uso de la linealidad del coeficiente de operador y $[x^{n+k}]A(x)=[x^n]x^{-k}A(x)$.

• En (3) aplicamos la regla de sustitución \begin{align*} A(x)=\sum_{k=0}^{\infty}a_kx^k=\sum_{k=0}^{\infty}x^k[y^k]A(y) \end{align*} con $a_k=[y^k]A(y)$.