Given a positive integer $ n $, let $ A, B $ be two co-prime positive integers such that $$ \frac{B}{A} = \left(\frac{n\left(n+1\right)}{2}\right)!\cdot\prod\limits_{k=1}^{n}{\frac{k!}{\left(2k\right)!}} $$Prove that $ A $ is a power of $ 2 $.
Problem
Source: 2019 Taiwan TST Round 1
Tags: factorial, number theory
02.04.2020 20:50
The proof proceeds in two steps:- STEP 1 (Proof that $2 \mid A$) Note that $$\frac{k!}{(2k)!}=\frac{1}{2^k(2k-1)!!} \text{ where } (2k-1)!!=1 \times 3 \times \dots \times (2k-1)$$which easily follows by taking out a factor of $2$ from all the even terms in the denominator. This gives us $$\frac{B}{A}=\left(\frac{n\left(n+1\right)}{2}\right)!\cdot\prod\limits_{k=1}^{n}{\frac{1}{2^k\left(2k-1\right)!!}}=2^{\frac{-n(n+1)}{2}} \cdot \left(\frac{n\left(n+1\right)}{2}\right)!\cdot\prod\limits_{k=1}^{n}{\frac{1}{\left(2k-1\right)!!}}$$But, by Legendre's Formula, we have $$\nu_2\left(\frac{n\left(n+1\right)}{2}\right)! \leq \frac{n(n+1)}{2}-1$$This directly gives that $2 \mid A$. STEP 2 (Proof that no odd prime divides $A$) It suffices to show that for all odd primes $p$, we have $$\nu_p \left(\left(\frac{n(n+1)}{2} \right)! \right)+\sum_{k=1}^n \nu_p(k!) \geq \sum_{k=1}^n \nu_p((2k)!)$$We will prove the following Lemma, after which the above claim directly follows using Legendre's Formula- LEMMA For all odd primes $p$, and positive integers $n$ and $z$, we have $$\left \lfloor \frac{n(n+1)}{2p^z} \right \rfloor+ \sum_{k=1}^n \left \lfloor \frac{k}{p^z} \right \rfloor \geq \sum_{k=1}^n \left \lfloor \frac{2k}{p^z} \right \rfloor$$ Proof of Lemma Let $n=ap^z+b$ with $0 \leq b<p^z$. We handle each term of the above expression seperately. \begin{align*} \left \lfloor \frac{n(n+1)}{2p^z} \right \rfloor &= \left \lfloor \frac{a^2p^{2z}+b^2+2abp^z+ap^z+b}{2p^z} \right \rfloor \\ &=ab+ \left \lfloor \frac{a^2p^z+a}{2} \right \rfloor+ \left \lfloor \frac{b(b+1)}{2p^z} \right \rfloor \\ &=ab+\frac{a^2p^z+a}{2}+\left \lfloor \frac{b(b+1)}{2p^z} \right \rfloor \\ \end{align*}where we use the fact that $a(ap^z+1)$ is always even for all odd $p$. Now, for the term $\sum_{k=1}^n \left \lfloor \frac{k}{p^z} \right \rfloor$, we add $a$ a total of $b+1$ times (for $k=ap^z,ap^z+1, \dots ,ap^z+b$) and add each of the terms $0,1, \dots, a-1$ a total of $p^z$ times. So we have \begin{align*} \text{LHS} &=\left(ab+\frac{a^2p^z+a}{2}+\left \lfloor \frac{b(b+1)}{2p^z} \right \rfloor \right)+a(b+1)+p^z(0+1+ \dots +(a-1)) \\ &=2ab+a+\frac{a^2p^z+a}{2}+\frac{a(a-1)p^z}{2}+\left \lfloor \frac{b(b+1)}{2p^z} \right \rfloor \\ &=2ab+\frac{3a}{2}+a^2p^z-\frac{ap^z}{2}+\left \lfloor \frac{b(b+1)}{2p^z} \right \rfloor \\ \end{align*} We turn our focus to the RHS, i.e. $\sum_{k=1}^n \left \lfloor \frac{2k}{p^z} \right \rfloor$. During this summation, the numerator consists of all even terms which are atmost $2ap^z+2b$. So for $k=ap^z,ap^z+1, \dots, ap^z+b$, the term $2a$ is added $b+1$ times along with the term $\sum_{k=0}^b \left \lfloor \frac{2k}{p^z} \right \rfloor$. Before these terms, we add each odd number less than $2a$ a total of $\frac{p^z-1}{2}$ times (i.e. when they leave remainders $1,3, \dots ,p^z-2$ modulo $p$). Similarly, we add each even number less than $2a$ a total of $\frac{p^z+1}{2}$ times (i.e. when they leave remainders $0,2, \dots ,p^z-1$ modulo $p^z$). So we have \begin{align*} \text{RHS} &=2a(b+1)+\frac{p^z-1}{2} \cdot (1+3+ \dots +(2a-1))+\frac{p^z+1}{2} \cdot (0+2+ \dots +(2a-2))+\sum_{k=0}^b \left \lfloor \frac{2k}{p^z} \right \rfloor \\ &= 2a(b+1)+\frac{1}{2}a^2(p^z-1)+\frac{1}{2}(a-1)a(p^z+1)+\sum_{k=0}^b \left \lfloor \frac{2k}{p^z} \right \rfloor \\ &= 2ab+\frac{3a}{2}+a^2p^z-\frac{ap^z}{2}+\sum_{k=0}^b \left \lfloor \frac{2k}{p^z} \right \rfloor \\ \end{align*}Comparing LHS and RHS found above, we have reduced our task to proving $$\left \lfloor \frac{b(b+1)}{2p^z} \right \rfloor \geq \sum_{k=0}^b \left \lfloor \frac{2k}{p^z} \right \rfloor \quad \forall \text{ } 0 \leq b \leq p^z-1$$If $b \leq \frac{p^z-1}{2}$, then the result is obvious (since then the RHS is zero, while the LHS is non-negative). So assume $b \geq \frac{p^z+1}{2}$. Then the RHS becomes $b-\frac{p^z-1}{2}$. Since this is an integer, so it suffices to prove that \begin{align*} \frac{b(b+1)}{2p^z} \geq b-\frac{p^z-1}{2} &\Longleftrightarrow b^2-(2p^z-1)b+p^z(p^z-1) \geq 0 \\ &\Longleftrightarrow (b-(p^z-1))(b-p^z) \geq 0 \\ \end{align*}which is obviously true since $b \leq p^z-1$. $\blacksquare$