Identity related to the totient function:$\sum\limits_{k=1}^n\phi(k)\left\lfloor \frac{n}{k}\right\rfloor = \frac{n(n+1)}{2}$

Question

Prove for every positive integer n the identity $$\phi(1)\left\lfloor \frac{n}{1}\right\rfloor + \phi(2)\left\lfloor \frac{n}{2}\right\rfloor + \phi(3)\lfloor \frac{n}{3}\rfloor + \dots+ \phi(n)\left\lfloor \frac{n}{n}\right\rfloor = \frac{n(n+1)}{2}$$

I was able to prove the above identity using induction. I am curious to know if there is any better proof without induction.

Answer 1

Well, one simple solution to the above problem would be to use the Gauss identity for the Euler totient function. We can write $$\frac{n(n+1)}{2} = \sum_{m=1}^{n} m = \sum_{m=1}^{n}\sum_{k \mid m}\phi(k) = \sum_{k=1}^{n}\phi(k)\sum_{m=1}^{\lfloor n/k \rfloor}1 $$ Proved.