Proof 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)} .$$
Problem
Source: 2021ChinaTST test3 day2 P1
Tags: number theory function, number theory, Innequality, floor function, inequalities
14.04.2021 05:16
Are you sure the problem is correct? Take n=3 then the problem is obviously wrong. I think it should be 3 instead of 5.
14.04.2021 05:38
Define \[\chi(n)=3^{\omega(n)}\qquad\phi(n)=\sum_{d\mid n}\tau(d)\qquad\psi(n)=3^{\Omega(n)}\]We have the following claim: Claim. \[\chi(n)\leq\phi(n)\leq\psi(n)\]Proof. This should be clear, as $\text c<\text h$ and $\text h<\text s$, so $\chi\leq\phi\leq\psi$. For an actual proof, we can notice all functions are multiplicative, so it suffices to check it for some prime power $p^k$. We can note \[\chi(p^k)=3^1=3\qquad\psi(p^k)=3^k\qquad\phi(p^k)=\sum_{d\mid p^k}\tau(d)=\sum_{n=0}^kn=\frac{k(k+1)}2\]so we have to prove \[3\leq\binom{k+1}2\leq 3^k\]for $k\geq 1$. The left bound is obvious, but to show the right, we will induct. Base Case. $k=1$. In this case, it reads $\binom 32\leq 3$, which is true. Induction Hypothesis. Assume the result holds for some $k\geq 1$. We show it for $k+1$. Induction Step. Note \[\binom{k+2}2\leq\binom{k+1}2\cdot\frac{k+2}{k+1}\leq\binom{k+1}2\cdot2<3^k\cdot 3=3^{k+1}\]thus completing this step. $\blacksquare$ To finish off, we note the left hand side is \[\sum_{m=1}^n\chi(n)\]and the right hand side is \[\sum_{m=1}^n\psi(n)\]Using the well known identity \[\left\lfloor\frac nk\right\rfloor=\sum_{d\mid k\leq n}1\]completing the proof.
14.04.2021 07:07
Justanaccount wrote: Are you sure the problem is correct? Take n=3 then the problem is obviously wrong. I think it should be 3 instead of 5. yes, it was wrong. I've corrected the mistake. apologize and @naman12 's proof is still available in a similar manner.
28.04.2021 16:49
Just for convenience, let me put the proof for the corrected problem here: The expression in the middle can be rewritten as \[\sum_{k=1}^n \sum_{d: dk \le n} \tau(k)^2=\sum_{m=1}^n \sum_{k \mid m} \tau(k)^2.\]Hence it suffices to prove that \[5^{\omega(n)} \le \sum_{d\le n} \tau(d)^2 \le 5^{\Omega(n)}.\]Since all three expressions are multiplicative in $n$, it suffices to consider $n=p^k$ where $p$ is a prime. The case $k=0$ is obvious. If $k \ge 1$, we need to prove that \[5 \le \sum_{j=1}^{k+1} j^2 \le 5^k.\]Here, again, the first inequality is obvious and the second one follows easily e.g. by induction.
26.07.2022 06:53
Solved with Sidharth Suresh and Malay Mahajan. 2021 China TST 3/2/4 wrote: Proof 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!
13.06.2023 19:31
Can anyone explain about functions ${\Omega(p)}$ ....
13.06.2023 19:36
Joider wrote: Can anyone explain about functions ${\Omega(p)}$ .... As far as I remember, $\omega(n)$ counts the number of prime factors of $n$ without multiplicity (counting each prime divisor once), whereas $\Omega(n)$ counts the prime divisors with multiplicity (counting each prime exactly as many times as it appears in $n$). For instance, if $n=p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}$, then $\omega(n)=k$ and $\Omega(n)=\alpha_1+\alpha_2+\cdots+\alpha_k$.
13.06.2023 20:10
Thank you