Demostrar que $\sum_{k=0}^{m}\dfrac{\binom{m}{k}}{\binom{n}{k}}=\dfrac{n+1}{n+1-m}$

Question

Demostrar que $\sum_{k=0}^{m}\dfrac{\binom{m}{k}}{\binom{n}{k}}=\dfrac{n+1}{n+1-m}$.

Sabemos que n > m. Del lado derecho. tenemos $\dfrac{n+1}{n+1-m}=\dfrac{1}{1-\dfrac{m}{n+1}}$. puesto que n > m. $0<\dfrac{m}{n+1}<1$. ¿Entonces $\dfrac{1}{1-\dfrac{m}{n+1}}=1+\dfrac{m}{n+1}+(\dfrac{m}{n+1})^2+...$ no sé qué hacer? ¿Elijo el camino correcto?

Answer 1

Puede resolver el problema siguiendo estos pasos:

1) en primer lugar mostrar que %#% $ #%

2) Mostrar ahora que %#% $ #%

3) Utilice los pasos 1 y 2 para demostrar que la ecuación que necesita es equivalente a probar

$$ \dfrac{\binom{m}{k}}{\binom{n}{k}} = \dfrac{\binom{n-k}{m-k}}{\binom{n}{m}}.$$

4) ahora demostrar la relación: $$ \binom{n}{m}\cdot\dfrac{n+1}{n+1-m} = \binom{n+1}{m}.$ $

4a) se puede demostrar a esta relación en varias formas. Uno de ellos es escribir $$ \sum_{k=0}^m\binom{n-k}{m-k} = \binom{n+1}{m}.$ $$ \sum_{k=0}^m\binom{n-k}{m-k} = \binom{n+1}{m}.$ y luego usar varias veces el % de relación $\binom{n-m}{0}$. Otro método es la inducción.

¡Mucha suerte!

Answer 2

He aquí una prueba probabilística.

Tenemos $n$ bolas en una bolsa, $m$ son blancos, $r=n-m$ son de color rojo. Hagamos el siguiente experimento: dibujamos un entero aleatorio $k$, distribuidos de manera uniforme en $0 \dots n$, y, a continuación, elegimos aleatoriamente $k$ bolas (sin reemplazo). Deje $W$ ser el caso de que todas las pelotas son de color blanco (más precisamente, de que ninguna bola es roja).

A continuación, $$P(W |k) = \frac{{m \choose k}}{{n \choose k}} [k\le m]$$ y $$P(W) = \sum_{k} P(W |k) P(k) =\frac{1}{n+1} \sum_{k=0}^m \frac{{m \choose k}}{{n \choose k}} \tag{1} $$

Alternativamente, nuestro experimento es equivalente a: producir una permutación aleatoria de la $n$ bolas, a continuación, compruebe si el primer $k$ bolas ($k$ dibuja como antes) son de color blanco. Que es lo mismo que decir: un lugar aleatorio de la barra entre las $n$ bolas ($n+1$ posiciones) y comprobar si se cae antes de la primera bola roja. Que es el mismo que el pensamiento de la barra como una nueva bola roja, y mirar si esta es la primera bola roja entre el total $r+1$ bolas rojas. Entonces

$$P(W)=\frac{1}{r+1}=\frac{1}{n-m+1} \tag{2}$$

Igualando (1) y (2) obtenemos el resultado deseado.

---

Una alternativa similar combinatoria manera: Tenemos $n+1$ bolas, $m$ blancos, $r=n-m$ rojo, y uno de naranja, de lo contrario, idénticos en ambos casos. Vamos a $C$ contar el número de maneras de colocar las bolas en $n+1$ de las células (numerados de $0$$n$), de modo que ninguna bola roja es antes de la naranja.

Sumando sobre todas las posiciones de la bola de color naranja, tenemos

$$C= \sum_{k=0}^m {n-k \choose m-k} ={n \choose m}\sum_{k=0}^m \frac{{m \choose k}}{{n \choose k}} \tag{3}$$

(por último igualdad de ver Isomorfismo de la respuesta).

Por otro lado, se puede considerar que la naranja-rojo bolas como un grupo (teniendo en cuenta la naranja distinguibles y colocando en primer lugar, es el mismo que condiring el grupo idénticos en ambos casos), lo que da ${n+1 \choose m}$ arreglos. Por lo tanto

$$C={n+1 \choose m} ={n \choose m} \frac{n+1}{n-m+1} \tag{4}$$

(de nuevo, por última igualdad véase el Isomorfismo de la respuesta).

Igualando (3) y (4) obtenemos el resultado deseado.

Answer 3

Usando el Método de Heaviside para fracciones parciales, obtenemos $$\begin{align} \sum_{k=0}^m\frac{\binom{m}{k}}{\binom{n}{k}} &=1+\sum_{k=1}^m\frac{m(m-1)(m-2)\dots(m-k+1)}{n(n-1)(n-2)\dots(n-k+1)}\tag{1}\\ &=1+m\sum_{k=1}^m\sum_{j=0}^{k-1}\frac{(-1)^{k-j-1}\binom{m-1}{k-1}\binom{k-1}{j}}{n-j}\tag{2}\\ &=1+m\sum_{k=1}^m\sum_{j=0}^{k-1}\frac{(-1)^{k-j-1}\binom{m-1}{j}\binom{m-j-1}{k-j-1}}{n-j}\tag{3}\\ &=1+m\sum_{j=0}^{m-1}\sum_{k=j+1}^m\frac{(-1)^{k-j-1}\binom{m-1}{j}\binom{m-j-1}{k-j-1}}{n-j}\tag{4}\\[6pt] &=1+\frac{m}{n-m+1}\tag{5}\\[6pt] &=\frac{n+1}{n-m+1}\tag{6} \end {Alinee el} $$ explicación:

$(1)$: romper el término de $k=0$ y expanda numerador y denominador
$(2)$: el método de Heaviside se aplica a la fracción en la suma
$(3)$: $\binom{m-1}{k-1}\binom{k-1}{j}=\binom{m-1}{j}\binom{m-j-1}{k-j-1}$
$(4)$: cambiar el orden de adición
$(5)$: $\sum\limits_{k=j+1}^m(-1)^{k-j-1}\binom{m-j-1}{k-j-1}=0^{m-j-1}=\big[j=m-1\big]$
$(6)$: adición