New types of inequalities.

Prove/disprove the following inequalities.

If MM and kk are natural numbers, then

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

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

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

Stay updated with my new inequality notes !!!

Note by A Former Brilliant Member
3 years, 9 months ago

No vote yet
1 vote

  Easy Math Editor

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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

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

proof:ϕ(nk)=nk1ϕ(n)ϕk(n)nk1ϕk1(n)nϕ(n)\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ϕ(n)n≥\phi(n) let n=ϕ(x)n=\phi(x) the ϕ(x)ϕ(ϕ(x))\phi(x)≥\phi(\phi(x)) and the result follows.

Aareyan Manzoor - 3 years, 9 months ago

Log in to reply

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

Otto Bretscher - 3 years, 9 months ago

Log in to reply

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

Mehul Arora - 3 years, 9 months ago

Log in to reply

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

Otto Bretscher - 3 years, 9 months ago

Log in to reply

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

A Former Brilliant Member - 3 years, 9 months ago

Log in to reply

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

ϕ(n)=n×(11a1)×(11a2)××1ak\phi (n) = n \times (1- \dfrac {1}{a_1}) \times (1- \dfrac {1}{a_2}) \times \cdots \times \dfrac {1}{a_k} where n=a1p1a2p2akpkn = a_1 ^{p_1} a_2 ^{p_2}\cdots a_k ^{p_k} where a1,a2....,aka_1,a_2...., a_k are prime numbers, and p1,p2...,pkp_1,p_2..., p_k are positive integers.

Now, ϕ(ϕ(n))=ϕ(n×(11a1)×(11a2)××1ak))\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 ϕ(n)<n\phi (n) < n , because it is multiplied by fractions less than 1.

Thus , we show that ϕ(ϕ(n))ϕ(n)\phi (\phi (n)) \leq \phi (n) , thus the inequality holds true.

Mehul Arora - 3 years, 9 months ago

Log in to reply

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

Otto Bretscher - 3 years, 9 months ago

Log in to reply

Oops yeah, thanks :D

Mehul Arora - 3 years, 9 months ago

Log in to reply

Nicely done Mehul !

A Former Brilliant Member - 3 years, 9 months ago

Log in to reply

Thanks Chinmay! :D

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

Mehul Arora - 3 years, 9 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...