Denote by $[n]!$ the product $ 1 \cdot 11 \cdot 111\cdot ... \cdot \underbrace{111...1}_{\text{n ones}}$.($n$ factors in total). Prove that $[n + m]!$ is divisible by $ [n]! \times [m]!$ (8 points)
Problem
Source:
Tags: factorial, function, floor function, number theory proposed, number theory
07.09.2010 17:52
First notice that \[\frac{[n+m]!}{[n]![m]!} = \frac{\prod_{i=1}^{n+m} (10^i-1)}{\prod_{i=1}^n (10^i-1)\cdot \prod_{i=1}^m (10^i-1)}.\] Second, notice that both numerator and denominator are co-prime to $10$. Let $p$ be any prime, different from $2$ and $5$, and let $r_k$ ($k=1,2,\dots$) be the multiplicative order of $10$ modulo $p^k$, then the $p$-adic valuation of the numerator is \[\sum_{k=1}^{\infty} \left\lfloor \frac{n+m}{r_k} \right\rfloor\] while that of the denominator is \[\sum_{k=1}^{\infty} \left\lfloor \frac{n}{r_k} \right\rfloor + \left\lfloor \frac{m}{r_k} \right\rfloor.\] It is clear that the former expression is not smaller than the latter, implying that the $p$-adic valuation of $\frac{[n+m]!}{[n]![m]!}$ is nonnegative. Since that holds for all primes (for $2$ and $5$ trivially), this fraction is an integer.
07.09.2010 18:19
Not so new...: http://en.wikipedia.org/wiki/Gaussian_binomial_coefficient
01.09.2018 13:25
I believe the problem boils down to showing $\dbinom{n+m}{m}_{10} \in \mathbb{Z}$ but it is a gaussian binomial coefficient so it is clearly true. I think it is strange that some technical theory can trivialize problem, but otherwise you are left to compare p-adic valuation
18.04.2021 12:24
One can notice that the problem boils down to showing that for any positive integers $n$ and $m$ $$\frac{(10^{n+1}-1)(10^{n+2}-1)\cdot\ldots\cdot(10^{n+m}-1)}{(10^{1}-1)(10^{2}-1)\cdot\ldots\cdot(10^{m}-1)}\in\mathbb{Z}$$In order to show this we induct on $m$. For $m=1$ the statement is clearly true. Suppose the claim is true for $m<k$ for some $k>1$ . We now prove it for $m=k$. For this purpose for any integers $n\geq 0$ and $m\geq 1$ we denote $$f(n,m)=\prod_{i=1}^{m}(10^{n+i}-1)$$and observe that $$f(n+1,m)-f(n,m)=f(n+1,m-1)(10^{n+m+1}-10^{n+1})$$By the induction hypothesis $f(n+1,m-1)$ is divisible by $f(0,m-1)$ and therefore $f(n+1,m)-f(n,m)$ is divisible by $f(0,m-1)(10^{m}-1)=f(0,m)$ . Therefore $f(n,m)=\sum_{i=0}^{n-1}(f(i+1,m)-f(i,m))+f(0,m)$ is clearly divisible by $f(0,m)$. The induction step is proved thus completing the proof of the statement.
25.12.2021 00:22
WLOG let $m\ge n,$ $x_i=\frac{10^i-1}{9},$ and $y_i=9x_i.$ Notice that $$\frac{[m+n]!}{[n]![m]!}=\frac{\prod_{i=1}^{m+n}x_i}{\prod_{i=1}^{m}x_i\prod_{i=1}^{n}x_i}=\frac{\prod_{i=1}^{m+n}y_i}{\prod_{i=1}^{m}y_i\prod_{i=1}^{n}y_i}=\frac{\prod_{i=m+1}^{m+n}y_i}{\prod_{i=1}^{n}y_i}=\binom{m+n}{n}_{10}$$and we are done. $\square$