# Induction on n allowed?

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?

• 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? – Arthur Nov 2 '17 at 7:45
• 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. – nobody Nov 2 '17 at 7:46
• 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. – Arthur Nov 2 '17 at 7:49
• 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? – nobody Nov 2 '17 at 7:51
• 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. – 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$.

• @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. – Especially Lime Nov 2 '17 at 8:26
• (The comment I was replying to has been deleted.) – Especially Lime Nov 2 '17 at 8:26
• Sorry I asked what was wrong in Test123 s proof, and then for some reason deleted it – nobody Nov 2 '17 at 8:35
• So basically Test123 s proof is "for all n, and for fixed m"? – nobody Nov 2 '17 at 8:37
• @EspeciallyLime Thanks for your comment. My answer was incomplete at that stage. I (believe) now I completed my answer. – 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$$
• I did the same. – nobody Nov 2 '17 at 8:14
• Here we are assuming that $r_i >0$ for each $i$ right? – nobody Nov 2 '17 at 8:15
• 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$ – nobody Nov 2 '17 at 8:31
• @namelessstudent Yes we assume that $0<r_i \leq n$. – Kal S. Nov 2 '17 at 8:33
• @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. – Kal S. Nov 2 '17 at 14:16