Demostrar que $\sum_{k=0}^{m}\binom{m}{k}\binom{n+k}{m}=\sum_{k=0}^{m}\binom{n}{k}\binom{m}{k}2^k$

Question

Demostrar que

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

¿Qué debo hacer para que esta ecuación? Debería centrarse en demostrar a $\binom{m}{k}\binom{n+k}{m}=\binom{n}{k}\binom{m}{k}2^k$?

Answer 1

Voy a estar usando una variedad de identidades por la suma de los coeficientes binomiales. Tenga en cuenta que los índices pueden variar a lo largo de todos los números enteros (no se preocupe acerca de los límites), ya que los sumandos es cero fuera del intervalo designado de todos modos.

1. Teorema Del Binomio: $2^k=\sum_{j} {k\choose j}$.
2. Sustituir en RHS: $\sum_k \sum_j {n\choose k}{m\choose k}{k\choose j}$.
3. Trinomio De Revisión: $\sum_k \sum_j {n\choose k}{m\choose j}{m-j\choose k-j}$.
4. Simetría: $\sum_k \sum_j {n\choose k}{m\choose j}{m-j\choose m-k}$.
5. El orden inverso de la suma: $\sum_j \sum_k {n\choose k}{m\choose j}{m-j\choose m-k}$.
6. Factor ${m\choose j}$: $\sum_j{m\choose j} \sum_k {n\choose k}{m-j\choose m-k}$.
7. Vandermonde identidad: $\sum_j{m\choose j}{n+m-j\choose m}$.
8. Simetría: $\sum_j{m\choose m-j}{n+m-j\choose m}$.
9. Sustituto $k=m-j$: $\sum_k{m\choose k}{n+k\choose m}$.
10. Y este es el lado izquierdo, como se desee.

Answer 2

Vamos a probar la identidad $$\sum_k\binom m{m-k}\binom{n+k}m=\sum_j\binom nj\binom m{m-j}2^j$$ combinatoria.

La reclamación. Deje $A$ $n$- element set y deje $B$ $m$- elemento del conjunto. Ambos lados contar el número de particiones $A$ en dos conjuntos, $A_1$$A_2$, e $B$ en dos conjuntos, $B_1$, $B_2$ y $B_3$, s.t. $|A_1|+|B_1|=m$.

Prueba. En el lado izquierdo primero escogemos $B_3$ (primer coeficiente binomial) y, a continuación, elija $A_1\cup B_1$ dentro $A\cup(B\setminus B_3)$ (segundo coeficiente binomial). En RHS elegimos $A_1\subset A$, $B_1\subset B$ y, finalmente,$B_2\subset(B\setminus B_1)$.

---

O, si prefiere la versión algebraica, esto es sólo $$ [t^m]\bigl\{(1+t)^n\bigl(1+(1+t)\bigr)^m\bigr\}= [t^m]\bigl\{(1+t)^n(2+t)^m\bigr\}. $$ Por supuesto, otros coeficientes son iguales, por lo que de inmediato una ligera generalización, $$ \sum_k\binom mk\binom{n+k, l}=\sum_j\binom nj\binom m{l-j}2^j $$ (que, después de un momento de reflexión, también es claro desde el puramente combinatoria prueba anterior).

Answer 3

Esto también se puede hacer con un básico de variables complejas técnica. Supongamos que buscamos para comprobar que $$\sum_{k=0}^m {m\elegir k} {n+k\elegir m} = \sum_{k=0}^m {m\elegir k} {n\elegir k} 2^k.$$

Introducir las dos representaciones integral $${n+k\elegir m} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} (1+z)^{n+k} \; dz$$ y $${n\elegir k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} (1+z)^n \; dz$$

Esto le da la siguiente integral por la suma en el lado izquierdo $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{k=0}^m {m\elegir k} \frac{1}{z^{m+1}} (1+z)^{n+k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{m+1}} \sum_{k=0}^m {m\elegir k} (1+z)^k \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{m+1}} (2+z)^m \; dz.$$

Obtenemos la siguiente integral por la suma en el lado derecho $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{k=0}^m {m\elegir k} 2^k \frac{1}{z^{k+1}} (1+z)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z} \sum_{k=0}^m {m\elegir k} 2^k \frac{1}{z^k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z} \left(1 + \frac{2}{z}\right)^m \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z} \frac{(z+2)^m}{z^m} \; dz.$$

Podemos detener aquí sin una evaluación adicional debido a las integrales para LHS y RHS se considera ser el mismo.

Un seguimiento de cuándo este método apareció en el MSE, y por el que se inicia en este MSE enlace.

Answer 4

Puedo ver que el propósito en el lado izquierdo de la eqn como:

Deje $A = {x_{1},x_{2},...,x_{n}}$$B={y_{1},y_{2},...,y_{m}}$. donde $n \ge m$

$ \left( \begin{array}{cc} m \\ 0 \\ \end{array} \right) $ $ \left( \begin{array}{cc} n \\ m \\ \end{array} \right) $ accounts the number of ways to choose $m$ elements from $$.

$ \left( \begin{array}{cc} m \\ 1 \\ \end{array} \right) $ $ \left( \begin{array}{cc} n + 1 \\ m \\ \end{array} \right) $ accounts the number of ways to choose $m$ elements from $$ plus one element from $B$. ( from the set {${x_{1},x_{2},...,x_{n},y_{i}}$} )

Seguir adelante hasta que el último término, $ \left( \begin{array}{cc} m \\ m \\ \end{array} \right) $ $ \left( \begin{array}{cc} n + m \\ m \\ \end{array} \right) $ accounts the number of ways to choose $m$ elements from $$ and $B$. ( from the set {${x_{1},x_{2},...,x_{n},y_{1},y_{2},...,y_{m}}$} )

$$ $$

Ahora por el lado derecho de la eqn, contar lo mismo como antes :

Establecer el número de $x_{i}$'s que ha sido elegido es $j$, luego el resto de la $m-j$ son elementos de $B$. Que es

$ \left( \begin{array}{cc} n \\ j \\ \end{array} \right) $ $ \left( \begin{array}{cc} m \\ m-j \\ \end{array} \right) $ = $ \left( \begin{array}{cc} n \\ j \\ \end{array} \right) $ $ \left( \begin{array}{cc} m \\ j \\ \end{array} \right) $

Acerca de la $2^k$ todavía estoy confundido, pero espero que esto ayude un poco.