Problem solving in NT ( day 4 Week 1)

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!!!