×

# New types of inequalities.

Prove/disprove the following inequalities.

If $$M$$ and $$k$$ are natural numbers, then

$1) \sum_{n=1}^{M} \phi(n) \geq \frac{1}{\sum_{n=1}^{M} \phi (n)}$

$2)\sum_{n=1}^{M} \phi(n) \geq \sum_{n=1}^{M} \phi(\phi(n))$

Notation: $$\phi(\cdot)$$ denotes Euler's totient function.

6 months, 4 weeks ago

Sort by:

1. since the sum on the LHS is ≥1, it is ≥ its reciprocal.

2. Lemma:$$\phi(n^k)≥\phi(n)^k$$

proof:$$\phi(n^k)=n^{k-1}\phi(n)≥\phi^k(n)\to n^{k-1}≥\phi^{k-1}(n)\to n≥\phi(n)$$ which we know is true. the result follows

3.$$n≥\phi(n)$$ let $$n=\phi(x)$$ the $$\phi(x)≥\phi(\phi(x))$$ and the result follows. · 6 months, 4 weeks ago

Darn I worked so hard to type the whole solution.

Thank god I started from the bottom, otherwise I would've worked harder, only to receive nothing :P · 6 months, 4 weeks ago

right, exactly. The only non-trivial one is $$\phi(n^k)=n^{k-1}\phi(n)$$ · 6 months, 4 weeks ago

Q3. We will prove that $$\phi (n) > \phi (\phi (n))$$

$$\phi (n) = n \times (1- \dfrac {1}{a_1}) \times (1- \dfrac {1}{a_2}) \times \cdots \times \dfrac {1}{a_k}$$ where $$n = a_1 ^{p_1} a_2 ^{p_2}\cdots a_k ^{p_k}$$ where $$a_1,a_2...., a_k$$ are prime numbers, and $$p_1,p_2..., p_k$$ are positive integers.

Now, $$\phi (\phi (n)) = \phi (n \times (1- \dfrac {1}{a_1}) \times (1- \dfrac {1}{a_2}) \times \cdots \times \dfrac {1}{a_k}))$$

We observe that $$\phi (n) < n$$ , because it is multiplied by fractions less than 1.

Thus , we show that $$\phi (\phi (n)) \leq \phi (n)$$ , thus the inequality holds true. · 6 months, 4 weeks ago

Nicely done Mehul ! · 6 months, 4 weeks ago

Thanks Chinmay! :D

I was about to write the other proofs as well, but Aareyan beat me ;) · 6 months, 4 weeks ago

oh , want some more ? actually I didn't know that 2nd one was a lemma , .... · 6 months, 4 weeks ago

Small correction : $$\phi(n)\leq n$$ since you have equality for $$n=1$$ · 6 months, 4 weeks ago

Oops yeah, thanks :D · 6 months, 4 weeks ago

I thought about them during my morning shower, and they all appear to be true. Want any proofs? They are all one liners... · 6 months, 4 weeks ago

Morning shower is the best place to think abt maths , ;) , Actually I thought abt them and their proofs , in my morning shower · 6 months, 4 weeks ago

Comment deleted 6 months ago

Post them*

I have* :P · 6 months, 4 weeks ago