Such a cute problem, although again, swapping the sum is hard.. I should practice more in that area 🙁
Solved with Sidharth and Malay!
Problem[2021 China TST 3/2/4]
Prove that
$$ \sum_{m=1}^n5^{\omega (m)} \le \sum_{k=1}^n\lfloor \frac{n}{k} \rfloor \tau (k)^2 \le \sum_{m=1}^n5^{\Omega (m)} .$$
Proof: Note that the middle term can be manipulated and written as $$\sum_{k=1}^n\lfloor \frac{n}{k} \rfloor \tau (k)^2= \sum_{k=1}^{n}\sum_{dk\le n}1 \tau(k)^2=\sum_{m=1}^n\sum_{k|m}\tau(k)^2$$
Since $\tau (k)$ is multiplicative, we get that $\tau(k)^2$ is multiplicative. Hence $F(m)= \sum_{k|a}\tau(k)^2$ is multiplicative too. ( As it’s $1* \tau(k)^2$)
Now, we begin our claim which proves the problem.
Claim: $5^{\omega(a)}\le \sum_{k|a}\tau(k)^2\le 5^{\Omega(a)}$
Proof: Note that these symbols are multiplicative, we just have to check for primes. For primes $p^b$, $$5^{\omega(p^b)}\le \sum_{k|p^b}\tau(k)^2\le 5^{\Omega(p^b)}$$
Or showing $$5 \le \frac{(b+1)(b+2)(2b+3)}{6} \le 5^b$$ which is true.
And we are done!
Yeyyyy!!!
