# 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 Brilliant Member
2 years, 8 months ago

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.

- 2 years, 8 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

- 2 years, 8 months ago

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

- 2 years, 8 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.

- 2 years, 8 months ago

Nicely done Mehul !

- 2 years, 8 months ago

Thanks Chinmay! :D

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

- 2 years, 8 months ago

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

- 2 years, 8 months ago

Oops yeah, thanks :D

- 2 years, 8 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...

- 2 years, 8 months ago

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

- 2 years, 8 months ago

Comment deleted Mar 02, 2016

Post them*

I have* :P

- 2 years, 8 months ago