Inducción sobre n?

Question

Para demostrar que ${{n}\choose{r_1}}{{n-r_1}\choose{r_2}}{{n-r_1-r_2}\choose{r_3}}...{{n-r_1-r_2-...-r_{m-1}}\choose{r_m}}=\frac{n!}{r_1!r_2!...r_m!}$ donde $r_1+r_2+...r_m=n$.

He probado el uso de la inducción en $n$. Pero mi profesora dice que la inducción no puede ser hecho por $n$ porque hay algún problema bien-definido-dad de que $m$ se ha tomado. Puede alguien explicar por qué se produce el problema?

Answer 1

No se puede probar por inducción en $n$, debido a $m \leq n$. En particular, durante su inducción paso, usted está demostrando nada acerca de $m$, por ejemplo, sabes que es verdad para $n=1,m=1$, y al mostrar que la verdadera para $n$ implica cierto para $n+1$, usted no está haciendo nada acerca de $m$ implica $m+1$.

Por otro lado, si se hizo la inducción en $m$, las cosas iban a salir bien, por $n$ está ligado a $m$; si aumenta el $m$$n+1$, eventualmente cubrir el caso para todos los $n \in \mathbb{N}$. Observe cómo este no es el caso anterior: si la inducción en $n$, usted sólo tenga cubierto el caso de, por ejemplo, $m = 1$.

Answer 2

Inducción en $n$ no dar una respuesta completa. El problema es que en la inducción paso que va de $n$ $n+1$saltar un argumento importante que se requiere para hacer algunas hipótesis sobre el valor de $m$.. Por ejemplo a continuación en la inducción de paso tenemos $m+1$, pero hay un oculto de inducción en $m$ no necesario para obtener una respuesta completa. Inducción en $m$ se requiere ya que el $n$ es simplemente la suma de los $r_i$'s.

---

Inducción en $n$ (respuesta incompleta):

Primero que nada, debemos asumir que $r_i \neq 0$. - Para $n=1$ se mantiene. Para$r_i>0$, $m=1$ es decir $r_1=n$. - Supongo que sostiene a $n$. - Tenemos que mostrar que tiene para $n+1$ es decir $LHS=RHS$, donde: $$ LHS={{n+1}\choose{s_0}}{{n+1-s_0}\choose{s_1}}{{n+1-s_0-s_1}\choose{s_2}}...{{n+1-s_0-s_1-s_2-...-s_{m-1}}\choose{s_m}} $$ $$ RHS=\frac{(n+1)!}{s_0!s_1!s_2!...s_m!} $$

Desde $s_1+\dots + s_m +s_0=n+1$, $s_1+\dots + s_m \leq n.$

Así que por hipótesis de inducción tenemos para$k=n+1-s_0$, $$s_1+\dots +s_m=k,$ $ y

$$ {{k}\choose{s_1}}{{k-s_1}\choose{s_2}}{{k-s_1-s_2}\choose{s_3}}...{{k-s_1-s_2-...-s_{m-1}}\choose{s_m}}=\frac{k!}{s_1!s_2!...s_m!} $$ Por lo tanto llegamos a la conclusión de que: $$ LHS = {{n+1}\, seleccione{s_0}}\frac{k!}{s_1!s_2!...s_m!}=\frac{(n+1)!}{s_0!k!}\frac{k!}{s_1!s_2!...s_m!}=RHS $$

---

NOTA: Para obtener una respuesta completa uno tiene que discutir sobre el valor de $m$. Podemos re-escribir la pregunta de la siguiente manera: Deje $n$ se define como $r_1+r_2+...r_m$ donde $r_i>0$ enteros.

Inducción en $m$ (respuesta completa):

• Para $m=1$ tiene trivialmente.
• Supongamos que se tiene para $m$. Tenemos que mostrar que tiene para $m+1$ es decir $LHS=RHS$ donde: $$ LHS={{N}\choose{r_1}}{{N-r_1}\choose{r_2}}...{{N-r_1-r_2-...-r_{m-1}}\choose{r_m}}{{N-r_1-r_2-...-r_{m-1}-r_m}\choose{r_{m+1}}} $$ $$ RHS=\frac{N!}{r_1!r_2!...r_m!r_{m+1}!} $$ WLOG supongamos $r_{m+1}$ tiene el valor más pequeño de la $r_i$'s. Deje $n=r_1+\dots +r_m$. Deje $s_1=r_1-r_{m+1}$. Entonces tenemos tha: $$ LHS = {{n+r_{m+1}}\choose{r_1}}{{n-s_1}\choose{r_2}}...{{n-s_1-r_2-...-r_{m-1}}\choose{r_m}}{{n-s_1-r_2-...-r_{m-1}-r_m}\choose{r_{m+1}}} \\ = {{ n+r_{m+1}}\elegir{r_1}} \frac{\frac{n!}{s_1!r_2!\puntos de r_m!r_{m+1}!}}{ {{n}\, seleccione{s_1}}} = \frac{N!}{r_1!(n-(r_1-r_{m+1}))!} \frac{n!}{s_1!r_2!\puntos de r_m!r_{m+1}!}\frac{s_1! (n-s_1)!}{n!}=RHS $$