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?

  • 2
    $\begingroup$ Wouldn't it be easier to prove just using the formula for the binomial terms directly and see that a lot of the factors cancel? $\endgroup$ – Arthur Nov 2 '17 at 7:45
  • $\begingroup$ Yes its easy to prove that way... but I want to apply induction because the question was asked in my examination to prove it by induction. $\endgroup$ – nobody Nov 2 '17 at 7:46
  • $\begingroup$ Well, then perhaps induction on $m$ rather than $n$ would be the easier way to go, since the connection between one case and the next is much stronger for $m$ than it is for $n$. At any rate, when you write out the formula as I suggested in the comment above and cancel terms, induction on $m$ is actually what you do; it hides in the $\cdots$. Writing it out explicitly as n induction might be good practice, though, and show your teacher that you know what you're doing. $\endgroup$ – Arthur Nov 2 '17 at 7:49
  • $\begingroup$ Yes induction on m is easy to do. But the question I am asking is whether induction on n is a wrong thing to do or not? $\endgroup$ – nobody Nov 2 '17 at 7:51
  • $\begingroup$ Also, when I fix n the m is not really varying over all natural numbers, unless you have all except finitely many $r_i$s are 0. $\endgroup$ – nobody Nov 2 '17 at 7:53

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$.

  • $\begingroup$ @namelessstudent Test123's proof is (almost) correct, but it is really a proof by induction on $m$ in disguise. (In fact it is has the wrong base case; you actually need the base case $m=1$.) You can't do induction purely based on $n$, for the reason Ken gives: $m$ must change too. $\endgroup$ – Especially Lime Nov 2 '17 at 8:26
  • $\begingroup$ (The comment I was replying to has been deleted.) $\endgroup$ – Especially Lime Nov 2 '17 at 8:26
  • $\begingroup$ Sorry I asked what was wrong in Test123 s proof, and then for some reason deleted it $\endgroup$ – nobody Nov 2 '17 at 8:35
  • $\begingroup$ So basically Test123 s proof is "for all n, and for fixed m"? $\endgroup$ – nobody Nov 2 '17 at 8:37
  • $\begingroup$ @EspeciallyLime Thanks for your comment. My answer was incomplete at that stage. I (believe) now I completed my answer. $\endgroup$ – Kal S. Nov 2 '17 at 14:15

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 $$
  • $\begingroup$ I did the same. $\endgroup$ – nobody Nov 2 '17 at 8:14
  • $\begingroup$ Here we are assuming that $r_i >0$ for each $i$ right? $\endgroup$ – nobody Nov 2 '17 at 8:15
  • $\begingroup$ You used $s_0 \ge 1$. But I think that is okay, because if $s_0=0$ then the corresponding ${{n+1}\choose{s_0}}=1$ and in RHS we have $s_0!=1$ $\endgroup$ – nobody Nov 2 '17 at 8:31
  • $\begingroup$ @namelessstudent Yes we assume that $0<r_i \leq n$. $\endgroup$ – Kal S. Nov 2 '17 at 8:33
  • $\begingroup$ @namelessstudent I have now finished writing my answer. Earlier I posted only the first part about induction on $n$ which is an incomplete answer as discussed above. $\endgroup$ – Kal S. Nov 2 '17 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.