Proof multinomial coefficient is always no less than 1 by induction

199 Views Asked by At

The goal is to show

$$\binom{n}{k}:=\frac{n!}{k_1!k_2!...k_d!}\geq1$$ where $k=(k_1,k_2,..,k_d)$ multiindex of dimension $d$ with $|k|=n$.

It is easy to show the case for $d = 1,2$.

$d = 1 $ is trivial.

For $d = 2$, let's use the common symbols $$\frac{n!}{k!(n-k)!} = \frac{n(n-1)\dots(n-k+1)}{k!}\geq 1$$ since $(n-k)!$ cancel out and $n\geq k$.

The last step would be assume the statement valid for the case $d=p$.

Then for the case $d=p+1$, is it safe to claim that for each $k=(k_1,k_2,..,k_{p+1})$, there exist a $\tilde{k}=(\tilde{k}_1,..,\tilde{k}_p)$ such that

$$\tilde{k}_i = k_i\, , i=1,..,p-1$$ and

$$\tilde{k}_p = k_p+k_{p+1}.$$

Then from(actually the binomial case) $$\frac{\tilde{k}_p}{k_p!k_{p+1}!}\geq1$$

the proof is complete.

Are there any flaws hidden in the proof? Thanks.

2

There are 2 best solutions below

1
On BEST ANSWER

You proof seems OK. But I would write it as $$ \binom n{k_1,\ldots,k_d} =\binom {k_1+k_2\cdots+k_d}{k_1}\binom{k_2+\cdots+k_d}{k_2}\ldots\binom{k_{d-1}+k_d}{k_{d-1}}, $$ a product of binomial coefficients all${}\geq1$, so the result is integer and${}\geq1$. The identity I wrote follows by induction from $$ \binom {k_1+k_2\cdots+k_d}{k_1,\ldots,k_d} =\binom {k_1+k_2\cdots+k_d}{k_1,k_2,\cdots,k_{d-2},(k_{d-1}+k_d)}\binom{k_{d-1}+k_d}{k_{d-1}}. $$ The multinomial coefficient after the "=" in this last equation is what your proof applies induction to, renaming the lower indices to $\tilde k_1,\ldots,\tilde k_{d-1}$ (only the final one has changed from the $k_i$).

The advantage of the formulation I gave is mainly that it shows you have found out a bit more about multinomial coeffcients than just their positivity (their combinatorial interpretation shows that they are integer).

1
On

This is a nice proof sketch. It doesn't have flaws so much as missing details. How are you combining the inductive hypothesis with the binomial case result?