Problem on Euler's Phi function

Question

Let $S(n)$ be $S(n)=\left\{k\;\left|\;\left\{\frac{n}{k}\right\}\right.\geq \frac{1}{2}\right\}$,where $\{x\}$ is the fractional part of $x$

Prove that :

\begin{align} \sum_{k\in S(n)} \varphi(k)=n^2 \end{align}

maybe the fact \begin{align} \sum_{k \leq 2n}\left\lfloor{\frac{n}{k}+\frac{1}{2}}\right\rfloor \varphi(k)=\frac{3n^2+n}{2}\end{align}

and \begin{align} \sum_{k \leq 2n}\left\lfloor{\frac{n}{k}}\right\rfloor \varphi(k)=\frac{n^2+n}{2}\end{align}

can help, but I can't prove these two equations

---

Edited:Sorry that my question is to prove the two equation before, because I've already known how to relate the problem with these two equations, and I've also known how to prove the second equation from Identity involving Euler's totient function: $\sum \limits_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{n(n+1)}{2}$ but I can't solve the first one with the similar method.

Answer 1

I'll recall (as is more or less indicated in the link you provided) that for the second identity $$ \sum_{0<k\leq 2n}\left\lfloor\frac nk\right\rfloor \varphi(k)=\frac{n^2+n}2 $$ both sides can be interpreted as counting the integer pairs $(x,y)$ satifying $0\leq x<y\leq n$ as follows. The right hand side counts by fixed value of $y$, giving $1+2+\cdots+n=\frac{n(n+1)}2$. The left hand side (where clearly only values $k\leq n$ contribute) counts by the value of $k=y/\gcd(x,y)$, in other words by the denominator of the fraction $x/y$ after reducing it. For such a $k$ there are $\phi(k)$ possible values for $l=x/\gcd(x,y)$ (the corresponding numerator), and for given $(l,k)$ the number of pairs $(x,y)$ that reduce to it is equal to the number of multiples of $k$ that are${}\leq n$, which is $\lfloor\frac nk\rfloor$.

Now the first identity can be done by a slight variation of this. The crucial point is to interpret $\lfloor\frac nk+\frac12\rfloor$ as the number of odd multiples of $k$ that are${}\leq2n$, which is easily checked. This leads us to count integer pairs $(x,y)$ satifying $0\leq x<y\leq2n$ and not both even. Counting by fixing $y$, one gets combining the odd values of $y$ the contribution $1+3+5+\cdots+(2n-1)=n^2$, and combining the even values of $y$ the contribution $1+2+3+\cdots+n=\frac{n(n+1)}2$, all in all $\frac{3n^2+n}2$ which is it right hand side of your first identity. For the left hand side the argument is exactly as before: the reduced pair $(l,k)$ cannot have both components even, so every $k$ gives the same number $\phi(k)$ of reduced pairs as before, however we can take only odd multiples of any reduced pair, giving $\lfloor\frac nk+\frac12\rfloor\phi(k)$ contributions from a given $k$ (for this case values $n<k\leq2n$ do contribute).

As you probably already had observed, one has $\lfloor\frac nk+\frac12\rfloor-\lfloor\frac nk\rfloor=1$ if $k\in S(n)$ and the difference is $0$ otherwise, which easily leads to your initial result.

Answer 2

By induction. Use that

$$ \sum_{k \mid n} \varphi(k) = n $$

and

$$\varphi(2k) = \begin{cases} 2\varphi(k) & \textrm{if } k \textrm{ is even}\\ \varphi(k) & \textrm{if } k \textrm{ is odd} \end{cases} $$

Carefully looking at the difference between $S(n)$ and $S(n+1)$ gives:

$$ \sum_{k \in S(n+1)} \varphi(k) = \sum_{k \in S(n)} \varphi(k) + \sum_{k \mid 2n + 1}\varphi(k) + \sum_{\substack{k \mid n + 1 \\ (n+1)/k \textrm{ odd}}} \varphi(2k) - \sum_{k \mid n+1} \varphi(k)\\ = (n+1)^2 + \sum_{\substack{k \mid n + 1 \\ (n+1)/k \textrm{ odd}}} \varphi(2k) - n - 1. $$

Write $n + 1= 2^a m$ with $a \geq 0$ and $m$ odd. Then the remaining sum is

$$ \sum_{k \mid m} \varphi(2^{a+1}k) = 2^a \sum_{k \mid m} \varphi(k) = 2^a m = n+1. $$