Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove that for $n\ge 3$, $$\varphi(2)+\varphi(3)+\varphi(4)+\cdots+\varphi(n)\ge\dfrac{n(n-1)}{4}+1$$

where $\varphi$ is the Euler's totient function

I think we must use this $$\sum_{k=1}^{n}\varphi(k)=\dfrac{1}{2}\left(1+\sum_{k=1}^{n}\mu(k)\left[\dfrac{n}{k}\right]^2\right)$$

share|cite|improve this question
Certainly possible. Hardy and Wright, fifth edition, say your sum is $$ \frac{3 n^2}{\pi^2} + O(n \log n), $$ Theorem 330 on page 268. – Will Jagy Jun 4 '13 at 2:27
Thank you,But this is Math contest Problem,I think this problem have a elementary proof . – math110 Jun 4 '13 at 2:30
$\lfloor\frac{n}{k}\rfloor =\frac{n}{k}+\{ \frac{n}{k} \}$, where $\{ \frac{n}{k} \}$ is fractional part. – i707107 Jun 4 '13 at 2:44
Thank you,@i707107 Then ? – math110 Jun 4 '13 at 2:46
Actually $\lfloor\frac{n}{k}\rfloor =\frac{n}{k}-\{ \frac{n}{k} \}$. It is possible (but tedious) to prove this by expanding out the first $6$ non-zero terms of the RHS and crudely taking absolute values of the remaining terms. But maybe there is a nicer way to show that more pairs of numbers are relatively prime than not. – Erick Wong Jun 4 '13 at 5:25

In the following picture the black dots represent the grid points (below the line $x=y$) that are visible from the origin, ie those for which there is no other grid point in the segment joining the point and the origin.

visible points

Within the triangle there are exactly $\varphi(k)$ black dots in the $k$th column, say those with coordinates $(a,k)$ with $\gcd(a,k)=1$ and $1 \le a \le k$, as a consequence the number of black dots in a triangle $T(n)$ with corners $(2,1),(n,1)$ and $(n,n-1)$ (including the borders) is exactly $$ B(n) = \varphi(2) + \varphi(3) + \dots + \varphi(n)$$ Call $W(n)$ the number of white dots in the triangle then $$ W(n) = 1-\varphi(2) + 2-\varphi(3) + \dots + n-1-\varphi(n) = \frac{n(n-1)}2 - B(n)$$

Given $n>3$ Consider the two triangles $T(n)$ and $T(\lfloor n/2 \rfloor)$, the second is represented with the green area, and the first with yellow and green areas.

We are going to show that the number of white dots in the big triangle $T(n)$ is at most $$ 2 B(\lfloor n/2 \rfloor) + 2 W(\lfloor n/2 \rfloor) = \lfloor n/2 \rfloor(\lfloor n/2 \rfloor-1) $$ we consider the lines going throug the origin and a white dot we have the following facts:

1) every such line cointains exacly a black dot, and it is in the green area.

2) the number of grid points in the line inside the yellow area is at most one more than the number of grid points in the line inside the green area.

As a consequence the number of white dots in the yellow area is at most equal to $B(\lfloor n/2 \rfloor)+W((\lfloor n/2 \rfloor)$ (the total number of points in the green triangle) plus $B(\lfloor n/2 \rfloor)$ the total number of lines going through white dots). Adding the number of white dots in the green triangle we obtain that the totla number of white dots in the big triangle is bounded by

$$2 (B(\lfloor n/2 \rfloor) + W(\lfloor n/2 \rfloor) = \lfloor n/2 \rfloor((\lfloor n/2 \rfloor-1) $$

So the number of black dots in the big triangle verifies:

$$B(n) \ge \frac{n(n-1)}2 - \lfloor n/2 \rfloor((\lfloor n/2 \rfloor-1) $$

if $n\ge 4$ then the right hand side is at least $$ \frac{n(n-1)}2 - \frac n2 \left(\frac n2-1\right) = \frac{n^2}4 \ge \frac{n(n-1)}4 + \frac{n}{4} \ge \frac{n(n-1)}4 + 1 $$ as was to be proved.

EDIT: I have rewritten the proof as the original was very confusing and contained some incorrect statements.

share|cite|improve this answer

This is only a partial answer, just a possibly profitable approach.

On the rhs we have an expression which contains just the half of the sum of consecutive numbers (with a small deviation), so I would try the problem comparing the double of the sum of totients with that of the natural numbers.
The conjecture is $$ \varphi(2) + \varphi(3) + ... + \varphi(n) \ge {n(n-1)\over 4} + 1 = {n(n+1)\over 2} \frac12 - \frac n2+1 $$ The $\varphi(\cdot)$ and the expression for the sum-of-consecutive-numbers expanded gives $$ 2\cdot(1-\frac12) + 3\cdot(1-\frac13)+4\cdot(1-\frac12)+...+ \varphi(n) \ge (1+2+3+4+...+n)(1-\frac12) - \frac n2 +1 $$ and we see, that most of the parentheses on the lhs evaluate to more than $(1-\frac12)=\frac12$
To simplify multiply both sides by 2 to get $$ (2 + 3 \cdot\frac43+4 + 5 \cdot\frac85 + 6 \cdot\frac 23 + 7 \cdot\frac {12}7 +...+2 \varphi(n)) \ge (1+2+3+4+...+n) - n +2 $$ Then we get first $$(2 + (3 +1)+4 + (5 +3)+ (6 - 6/3) + (7 + 5)+...+2 \varphi(n)) \ge (1+2+3+4+...+n) - n +2 $$ and separating the lhs in two parentheses $$ \begin{eqnarray} && (2 + 3 +4 + 5 + 6 + 7+...+ n) \\ &+ & (0+1+0+3-2+5+0+3... + 2 \varphi(n)-n ) \\ &\ge & (1+2+3+4+...+n) & - n +2 \end{eqnarray} $$ and finally $$ 0+1+0+3-2+5+0+3 + \ldots + 2\varphi(n) \ge 3 $$ The problem reduces then to show, that the partial sums of the lhs-expression are always positive and $\ge 3$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.