To prove that ${{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!}$ where $r_1+r_2+...r_m=n$.
I have proved this using induction on $n$. But my professor says that induction can not be done by $n$ because there is some problem for well-defined-ness of which $m$ is taken. Can someone explain why the problem occurs?
$\endgroup$ 52 Answers
$\begingroup$You can't prove by induction on $n$, because $m \leq n$. In particular, during your induction step, you are proving nothing about $m$, e.g. you know it's true for $n=1,m=1$, and when you show that true for $n$ implies true for $n+1$, you are not doing anything about $m$ implies $m+1$.
On the other hand, if you did induction on $m$, things would work out because $n$ is tied to $m$; if you increase $m$ to $n+1$, you will eventually cover the case for all $n \in \mathbb{N}$. Notice how this isn't the case earlier: if you do induction on $n$, you might have only covered the case of, say, $m = 1$.
$\endgroup$ 5 $\begingroup$Induction on $n$ won't provide a complete answer. The problem is that at the induction step going from $n$ to $n+1$ you skip an important argument required for making some assumption on the value of $m$.. For example below at the induction step we have $m+1$ but there is a hidden induction on $m$ there required for a complete answer. Induction on $m$ is required since $n$ is simply defined the sum of the $r_i$'s.
Induction on $n$ (incomplete answer):
First we may assume that $r_i \neq 0$. - For $n=1$ it holds. For $r_i>0$, we have $m=1$ namely $r_1=n$. - Suppose it holds up to $n$. - We need to show that it holds for $n+1$ i.e. $LHS=RHS$, where: $$ 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!} $$
Since $s_1+\dots + s_m +s_0=n+1$, we have that $s_1+\dots + s_m \leq n.$
So by induction hypothesis we have for $k=n+1-s_0$, that $$s_1+\dots +s_m=k,$$ and
$$ {{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!} $$ Hence we conclude that: $$ LHS = {{n+1}\choose{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 $$
NOTE: For a complete answer one has to argue about the value of $m$. We can re-write the question as follows: Let $n$ be defined as $r_1+r_2+...r_m$ where $r_i>0$ integers.
Induction on $m$ (complete answer):
- For $m=1$ it holds trivially.
- Suppose that it holds for $m$. We need to show that it holds for $m+1$ namely $LHS=RHS$ where: $$ 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 suppose $r_{m+1}$ has the smallest value of the $r_i$'s. Let $n=r_1+\dots +r_m$. Let $s_1=r_1-r_{m+1}$. Then we have 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}}\choose{r_1}} \frac{\frac{n!}{s_1!r_2!\dots r_m!r_{m+1}!}}{ {{n}\choose{s_1}}} = \frac{N!}{r_1!(n-(r_1-r_{m+1}))!} \frac{n!}{s_1!r_2!\dots r_m!r_{m+1}!}\frac{s_1! (n-s_1)!}{n!}=RHS $$
