Taiwan IMO Selection Camp

It suffices to prove that for all primes $p \ge 3$, we have
$$\sum_{i=1}^{\infty} \left( \left[ \frac{n(n+1)}{2p^i} \right] + \sum_{k=1}^{n} \left( \left[ \frac{k}{p^i} \right] - \left[ \frac{2k}{p^i} \right] \right) \right) \ge 0$$

Note that $[2x] = [x] + [x + \frac{1}{2}]$, so it suffices to prove for every positive integer $i$ that
$$\left[ \frac{n(n+1)}{2P} \right] \ge \sum_{k=1}^{n} \left[ \frac{k}{P} + \frac{1}{2} \right]$$

where $P = p^i$ is odd.

Case 1. $n = Pa + b, \ 0 \le b \le \frac{P-1}{2}$,
$$\begin{aligned} \text{R.H.S.} &= \sum_{k=1}^{n} \left(\frac{k}{P} + \frac{1}{2}\right) - \frac{P}{2} \cdot a - \sum_{k=1}^{b} \left(\frac{k}{P} + \frac{1}{2}\right) \\ &= \frac{n(n+1)}{2P} + \frac{n}{2} - \frac{Pa}{2} - \frac{b(b+1)}{2P} - \frac{b}{2} \\ &= \frac{n(n+1)}{2P} - \frac{b(b+1)}{2P} \end{aligned}$$

Since $\frac{n(n+1)}{2} \equiv \frac{b(b+1)}{2} \pmod{P}$, we have
$$\text{L.H.S.} = \left[ \frac{n(n+1)}{2P} \right] \ge \frac{n(n+1)}{2P} - \frac{b(b+1)}{2P} = \text{R.H.S.}$$

Case 2. $n = Pa + \frac{P-1}{2} + b, \ 1 \le b \le \frac{P-1}{2}$,
$$\begin{align*} \text{R.H.S.} &= \sum_{k=1}^{n} \left[ \frac{P+2k}{2P} \right] \\ &= \sum_{k=1}^{n} \left( \frac{k}{P} + \frac{1}{2} \right) - \frac{P}{2} \cdot a - \sum_{k=1}^{\frac{P-1}{2}} \left( \frac{k}{P} + \frac{1}{2} \right) - \sum_{k=1}^{b} \frac{2k-1}{2P} \\ &= \frac{n(n+1)}{2P} + \frac{n}{2} - \frac{Pa}{2} - \frac{1}{2P} \cdot \frac{P-1}{2} \cdot \frac{P+1}{2} - \frac{1}{2} \cdot \frac{P-1}{2} - \frac{b^2}{2P} \\ &= \frac{n(n+1)}{2P} - \left( -\frac{b}{2} + \frac{1}{2P} \cdot \frac{P-1}{2} \cdot \frac{P+1}{2} + \frac{b^2}{2P} \right) \end{align*}$$

$$\begin{align*} n(n+1) &= \left(Pa + \frac{P-1}{2} + b\right)\left(Pa + \frac{P+1}{2} + b\right) \\ &= a^2 P^2 + aP \cdot (P + 2b) + \left(\frac{P-1}{2} + b\right)\left(\frac{P+1}{2} + b\right) \\ &= (a^2 + a)P^2 + 2abP + \frac{P-1}{2} \cdot \frac{P+1}{2} + Pb + b^2 \\ &\equiv \frac{P-1}{2} \cdot \frac{P+1}{2} - Pb + b^2 \pmod{2P} \\ &\equiv \frac{(P-2b)^2 - 1}{4} \pmod{2P} \end{align*}$$

$$\begin{align*} \text{L.H.S.} &= \left[ \frac{n(n+1)}{2P} \right] \ge \frac{n(n+1)}{2P} - \frac{1}{2P} \left( \frac{(P-2b)^2-1}{4} \right) \\ &= \frac{n(n+1)}{2P} - \left( -\frac{b}{2} + \frac{1}{2P} \cdot \frac{P-1}{2} \cdot \frac{P+1}{2} + \frac{b^2}{2P} \right) \\ &= \text{R.H.S.}, \text{ Q.E.D.} \end{align*}$$