Que acrediten la identidad ${n \choose k} = {\sum\limits_{m=k-1}^{n-1} {m \choose k-1}}$ por inducción sobre t=n-k

Question

De la identidad de ${n \choose k} = {\sum\limits_{m=k-1}^{n-1} {m \choose k-1}}$, una prueba por inducción sobre $d=n-k$ debería ser posible. Sólo puedo ver cómo $${n+1 \choose k} = {n \choose k} + {n \choose k-1}$$ (por Pascal identidad)

$$ ={\sum_{m=k-1}^{n-1} {m \choose k-1}} + {n \choose k-1}$$ (by induction hypothesis) $$={\sum_{m=k-1}^{n} {m \choose k-1}}$$ lleva al resultado. Puede que alguien me apunte en la dirección correcta para una inducción sobre $d=n-k$?

Answer 1

Desde $d=n-k$, se puede volver a escribir como

$$\binom{d+k}k=\sum_{m=k-1}^{d+k-1}\binom{m}{k-1}\;;$$

deje $\ell=m-(k-1)$, y esto a su vez puede ser reescrita

$$\binom{d+k}k=\sum_{\ell=0}^d\binom{\ell+k-1}{k-1}\;,$$

y quieres probar esto por inducción en $d$. Sólo utilizar el mismo enfoque que tomó de su inducción en $n$.

Answer 2

Usted puede solicitar una prueba inductiva, pero no puedo resistir una combinatoria de prueba cuando la oportunidad se presenta.

La del lado izquierdo, $\binom{n}{k}$, cuenta el número de $k$-elemento subconjuntos del conjunto $\{1, 2, \dots, n\}$. Partición de la colección de todos los subconjuntos de acuerdo a su elemento más grande. Voy a demostrar.

El número de $k$-elemento subconjuntos cuyo elemento más grande es$k$$\binom{k-1}{k-1}$; elija $k-1$ elementos del conjunto $\{1, 2, \dots, k-1\}$ y, a continuación, incluir el elemento $k$. (Esto se puede hacer de una sola manera, por supuesto).

El número de $k$-elemento subconjuntos cuyo elemento más grande es$k+1$$\binom{k}{k-1}$; elija $k-1$ elementos del conjunto $\{1, 2, \dots, k\}$ y, a continuación, incluir el elemento $k+1$.

En general, el número de $k$-elemento subconjuntos cuyo elemento más grande es$m+1$$\binom{m}{k-1}$; elija $k-1$ elementos del conjunto $\{1, 2, \dots, m\}$ y, a continuación, incluir el elemento $m+1$. Suma más de $m$ da el deseo de identidad.