# 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. Note by A Former Brilliant Member
4 years, 9 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

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.

- 4 years, 9 months ago

right, exactly. The only non-trivial one is $\phi(n^k)=n^{k-1}\phi(n)$

- 4 years, 9 months 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

- 4 years, 9 months ago

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

- 4 years, 9 months ago

Morning shower is the best place to think abt maths , ;) , Actually I thought abt them and their proofs , in my morning shower

- 4 years, 9 months 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.

- 4 years, 9 months ago

Small correction : $\phi(n)\leq n$ since you have equality for $n=1$

- 4 years, 9 months ago

Oops yeah, thanks :D

- 4 years, 9 months ago

Nicely done Mehul !

- 4 years, 9 months ago

Thanks Chinmay! :D

I was about to write the other proofs as well, but Aareyan beat me ;)

- 4 years, 9 months ago