Simple method for $\frac{(2n+1)!}{(n!)^{2}}$ divide $lcm(1,2,\ldots,2n+1)$

Question

The question is to prove that $\frac{(2n+1)!}{(n!)^{2}}$ divides $lcm(1,2,\ldots,2n+1)$.

This seems like it should be a simple question, but try as I might, I can't seems to find any way that does not involve a complicated argument using prime factorization.

So anyone know any simple obvious method to prove this? Thanks a lot.

Answer 1

I'm not sure if you'd this argument complicated, but one way to prove the statement goes as follows:

Let $v_p(k)$ be the valuation of prime $p$ in number $k$; i.e. the highest power of $p$ which divides $k$. There are a few observations we can make:

• Every $p$-th integer contributes one occurrence of $p$ into prime factorization of $(n!)$. Every $p^2$-th contributes an additional $p$ and so on. This can be summarized as the equality $$v_p(n!) = \left\lfloor\frac{n}{p}\right\rfloor + \left\lfloor\frac{n}{p^2}\right\rfloor + \left\lfloor\frac{n}{p^3}\right\rfloor + \ldots = \sum\limits_{e\geq 1} \left\lfloor\frac{n}{p^e}\right\rfloor$$
• The the sum is infinite, but only first $\left\lfloor \log_p(n)\right\rfloor$ terms are non-zero.
• Similar reasoning applies to $$v_p((2n+1)!) = \sum\limits_{e\geq 1} \left\lfloor\frac{2n+1}{p^e}\right\rfloor$$ in which only first $\left\lfloor \log_p(2n+1)\right\rfloor$ terms are non-zero.
• For any positive integers $n$ and $k$, we have $$\left\lfloor\frac{2n+1}{k}\right\rfloor \leq 2\left\lfloor\frac{n}{k}\right \rfloor+1$$
• $v_p(a/b) = v_p(a) - v_p(b)$, so $$v_p\left(\frac{(2n+1)!}{(n!)^2}\right) = \sum\limits_{e\geq 1} \left(\left\lfloor\frac{2n+1}{p^e}\right\rfloor - 2\left\lfloor\frac{n}{p^e}\right\rfloor\right)\leq \lfloor\log_p(2n+1)\rfloor$$
• $v_p(\mathrm{lcm}(a,b)) = \max(v_p(a), v_p(b))$, so $$v_p(\mathrm{lcm}(1,2,\ldots,2n+1)) = \left\lfloor log_p(2n+1)\right\rfloor$$
• Number $a$ divides number $b$ if and only if for all primes $p$, we have $v_p(a)\leq v_p(b)$. But we have just shown that this holds for $\frac{(2n+1)!}{(n!)^2}$ and $\mathrm{lcm}(1,2,\ldots,2n+1)$; Q.E.D.