Trouble manipulating quotients in $\mathbb{N}^\times$

74 Views Asked by At

As part of a proof about multinomial expansions, I am encountering difficulty in showing the following equality: $$\frac{k!}{\alpha!} = \frac{(k-\alpha_1)!}{\alpha'!}\frac{k!}{\alpha_1!(k - \alpha_1)!},$$ where $k \in \mathbb{N}^\times$, $\alpha = (\alpha_1, ...,\alpha_{m+1}) \in \mathbb{N}^{m+1}$ for some $m \geq 2$, $\alpha' = (\alpha_2, ...,\alpha_{m+1})$, and where factorials of multinomial indices are defined as products of the factorials of their entries. I emphasize that I do not know a priori that $\alpha!$ even divides $k!$. I am hoping someone can show me the argument for this equality which will, in the end, by definition of quotients in the natural numbers result in the proof of the fact that $$k! = \left[\frac{(k-\alpha_1)!}{\alpha'!}\frac{k!}{\alpha_1!(k - \alpha_1)!} \right]\alpha!,$$ which will be enough by the uniqueness of quotients.

However, given that we are in $\mathbb{N}$ and not in $\mathbb{Q}$, I cannot just naively move things around in the numerator and denominator.

For context, I have supplied the proof which (at the end) has me stumped:

enter image description here enter image description here

1

There are 1 best solutions below

9
On BEST ANSWER

We seem to be working in a context in which $\mathbb{Q}$ has not been defined, so it's forbidden to mention quotients where the denominator does not divide the numerator. The usual algebraic laws though still hold whenever the quotients exist (as elements of $\mathbb{Z}$).

The screenshotted argument says it's an inductive proof; the part you're concerned with is the implication from case $m$ to case $m+1$. Here $\alpha=(\alpha_1,\ldots,\alpha_{m+1})$, $\alpha'=(\alpha_2,\ldots,\alpha_{m+1})$, and $k=\sum_{i=1}^{m+1}\alpha_i$. Note that $k-\alpha_1=\sum_{i=2}^{m+1}\alpha_i$ is the length of $\alpha'$. So case $m$ applies to the multi-index $\alpha'$, asserting that $$\frac{(k-\alpha_1)!}{\alpha'!}$$ is an element of $\mathbb{N}$.

So the product $$\frac{(k-\alpha_1)!}{\alpha'!}\binom{k}{\alpha_1}\in\mathbb{N}.$$ The text seems to have already established the formula for the binomial coefficient, so we're entitled to write $$\frac{(k-\alpha_1)!}{\alpha'!}\frac{k!}{(k-\alpha_1)!\alpha_1!}$$ for this product. Now as I said, the usual rules hold for quotients provided they all belong to $\mathbb{Z}$, so we can combine the product into one quotient and cancel the $(k-\alpha_1)!$. Since $\alpha!=\alpha_1!\alpha'!$ (just by writing out what these multi-index factorial symbols mean), this concludes the induction.

If you want a proof that $$\frac{A}{B}\frac{C}{D}=\frac{AC}{BD}$$ in $\mathbb{Z}$, in the sense that if the left side is well-defined, so is the right and then they are equal, that's not hard to do. Just write $$\begin{align}\frac{A}{B}=X&\Leftrightarrow A=BX\\ \frac{C}{D}=Y&\Leftrightarrow C=DY\\ \frac{AC}{BD}=XY&\Leftrightarrow AC=BDXY \end{align}$$ To be more explicit, if the left-hand-sides of the first two equations hold, then the right-hand-sides hold, and those RHS's imply the RHS of the third equation which then imply the LHS.

However, it doesn't work in the reverse direction. Easy counter-example: $\frac{1\cdot 2}{2\cdot 1}$ is an integer, but $\frac{1}{2}\frac{2}{1}$ is a fraction times an integer.

Likewise it's easy to show that $$\frac{CA}{CB}=\frac{A}{B}$$ if $C\neq0$, in the sense that if one side is well-defined in $\mathbb{Z}$ then so is the other, and then they are equal.