Spivak Cálculo del Ejercicio 4.una de 2º capítulo

Question

4 . (a) Probar que $$\sum_{k=0}^l \binom{n}{k} \binom{m}{l-k} = \binom{n+m}{l}.$$ Sugerencia: Aplique el teorema del binomio para $(1+x)^n(1+x)^m$.

Estoy teniendo un momento difícil tratando de resolver el problema anterior. He hecho todos los anteriores ejercicios del capítulo 2º con un poco de dificultad, hasta ahora. Creo que puede ser que falte un punto trivial en algún lugar.

---

La respuesta que obtuve del Libro de respuestas, y no es muy útil, ya sea... :(

4. (a) $(1+x)^n(1+x)^m = (1+x)^{n+m}$ tenemos $$\sum_{k=0}^n \binom{n}{k}x^k\cdot\sum_{j=0}^m \binom{m}{j}x^j\cdot=\sum_{l=0}^{n+m} \binom{n+m}{l}x^l$$ Pero el coeficiente de $x^l$ en el de la izquierda es claramente $$\sum_{k=0}^l\binom{n}{k}\binom{m}{l-k}.$$
Un término de la suma que se producen para cada par $k$, $j = l-k$.

Yo no podía obtener la última parte de la respuesta:
¿por qué es que el "coeficiente de $x^l$ en el de la izquierda es claramente $\sum_{k=0}^l\binom{n}{k}\binom{m}{l-k}$."?

Answer 1

Tal vez esto le ayudará a pensar acerca de los coeficientes. Tenemos $n$ niños y $m$ de las niñas, y queremos formar un comité de $l$ a las personas de estos $n+m$ de la gente. Claramente hay $\binom{n+m}{l}$ maneras de formar el comité.

Vamos a contar el número de comités de otra manera. Podríamos tener $0$ niños y $l$ niñas. Un comité puede ser formado en $\binom{n}{0}\binom{m}{l}$ maneras.

O podemos tener $1$ boy y $l-1$ niñas. Un comité puede ser formado en $\binom{n}{1}\binom{m}{l-1}$ maneras.

O podemos tener $2$ niños y $l-2$ niñas. Un comité puede ser formado en $\binom{n}{2}\binom{m}{l-2}$ maneras.

De continuar. El número total de comités $$\sum_{k=0}^l \binom{n}{k}\binom{m}{l-k}.\tag{$1$}$$ Pero ya hemos visto que el número de comités de es $\binom{n+m}{l}$.

Nota: es posible que, por ejemplo, hay un total de $3$ niños y $24$ de las niñas, y queremos formar un comité de $7$ de la gente. A continuación, la fórmula que aparece a romper. Pero no si estamos de acuerdo en que $\binom{a}{b}=0$ si $b\gt a$.

Para aplicar el razonamiento a $(1+x)^n(1+x)^m$, usted podría primer vistazo a $(1+x)^n(1+y)^m$, y establecer $y=x$ al final. Para ampliar tanto, se multiplican. Fijo $l$, de reunir a los términos que tienen un total combinado de $l$ $x$'s (chicos) y/o $y$'s. El número total estará dada por la Fórmula $(1)$.

Answer 2

La multiplicación de poder formal de la serie se realiza mediante la recopilación de los términos con los mismos poderes de $x$: $$ \begin{align} \left(\sum_{k=0}^\infty a_kx^k\right)\left(\sum_{k=0}^\infty b_kx^k\right) &=\sum_{k=0}^\infty\left(\sum_{j=0}^k a_j\color{#C00000}{x^j}b_{k-j}\color{#C00000}{x^{k-j}}\right)\\ &=\sum_{k=0}^\infty\left(\sum_{j=0}^k a_jb_{k-j}\right)\color{#C00000}{x^k}\tag{1} \end{align} $$ Tenga en cuenta que los subíndices en el interior de la suma agregar a a $k$, el poder de la $x$ en el exterior de la suma.

Se aplican $(1)$ al producto de $$ (1+x)^m=\sum_{k=0}^\infty\binom{m}{k}x^k\etiqueta{2} $$ y $$ (1+x)^n=\sum_{k=0}^\infty\binom{n}{k}x^k\etiqueta{3} $$ que es $$ (1+x)^{m+n}=\sum_{k=0}^\infty\binom{m+n}{k}x^k\etiqueta{4} $$ Extendí los índices en las sumas a $\infty$, ya que para $k>n$, $\binom{n}{k}=0$.

Para el producto de la $(2)$$(3)$, obtenemos $$ (1+x)^m(1+x)^n=\sum_{k=0}^\infty\left(\sum_{j=0}^k \binom{m}{j}\binom{n}{k-j}\right)x^k\etiqueta{5} $$ La comparación de los coeficientes de $x^k$ $(4)$ $(5)$ rendimientos $$ \binom{m+n}{k}=\sum_{j=0}^k \binom{m}{j}\binom{n}{k-j}\etiqueta{6} $$ como se desee.

Answer 3

Primera nota de que $\sum_{k=0}^n \binom{n}{k}x^k\cdot\sum_{j=0}^m \binom{m}{j}x^j = \sum_{k=0}^n \sum_{j=0}^m \binom{n}{k} \binom{m}{j}x^{k+j}$.

Ahora observe que la suma es sobre el conjunto de índices $\{(k,j) | k=0,...,n, \ j=0,...,m \}$. Usted necesita para convencerse de que este es el mismo como el conjunto de índices $\{ (p,l-p) | l=0,...,n+m,\ p=0,...,l \}$, así que podemos escribir

$$\sum_{k=0}^n \sum_{j=0}^m \binom{n}{k} \binom{m}{j}x^{k+j} = \sum_{l=0}^{n+m} \sum_{p=0}^l \binom{n}{p} \binom{m}{l-p}x^{l}.$$ Ahora tenemos $$\sum_{l=0}^{n+m} \sum_{p=0}^l \binom{n}{p} \binom{m}{l-p}x^{l} = \sum_{l=0}^{n+m} \binom{n+m}{l}x^l ,$$ que son polinomios de $x$ en ambos lados. Ya que esta igualdad es verdadera para todos los $x$, los polinomios son iguales y por lo tanto también lo son los coeficientes de cada una de las $x^l$ (diferenciar $l$ veces y establecer $x=0$ a convencer a ti mismo). De ello se sigue que $$\sum_{p=0}^l \binom{n}{p} \binom{m}{l-p} = \binom{n+m}{l} .$$

Answer 4

Si se multiplica $c_0+c_1x+\cdots+c_nx^n$$d_0+d_1x+\cdots+d_mx^m$, $k\leq\min(n,m)$ obtendrá términos relacionados con la $x^k$ a partir de los productos $c_0\times d_kx^k$, $\,c_1x\times d_{k-1}x^{k-1}$, $\,c_2x^2\times d_{k-2}x^{k-2}$,..., $c_kx^k\times d_0$, y de ningún otro producto. La adición de esas contribuciones da $(c_0d_k+c_1d_{k-1}+c_2d_{k-2}+\cdots+c_kd_0)x^k$. Incluso si uno debe tener $k>\min(n,m)$, el coeficiente de $x^k$ es claramente siempre que la suma de todos los $c_id_j$$i+j=k$, la cual se puede escribir como $\sum_{i=0}^kc_id_{k-i}$ siempre y cuando uno define el $c_i$ o $d_j$ $0$ cuando el subíndice es demasiado grande. Y en su ejemplo, el coeficiente binomial expresiones convertido de hecho, en $0$ cuando el índice inferior es demasiado grande.

Answer 5

Usted debe determinar el coeficiente de $x^l$ $(1+x)^n(1+x)^m$ en dos maneras. Primero se multiplica este a $(1+x)^n(1+x)^m=(1+x)^{n+m}$. Teniendo en cuenta el lado derecho y usando el teorema del binomio tenemos $\binom{n+m}{l}$.

Ahora, considere el coeficiente de $x^l$ en la mano izquierda después de la expansión de cada término usando el teorema del binomio $$(1+x)^n(1+x)^m=(\sum_{p=0}^m \binom{m}{p}x^p)(\sum_{q=0}^n \binom{n}{q}x^q)$$ You get a coefficient of $x^l$ in the product when you multiply $\binom{m}{p}x^p\binom{n}{p}x^q$ when $p+q=l$, i.e. $q=l-p$.

A continuación, hemos de tener en cuenta todas las formas en que esto puede suceder y compararlo con lo que tenemos en el lado derecho por lo que tenemos $$\sum_{p=0}^l\binom{m}{p}\binom{n}{l-p}=\binom{m+n}{l}$$