2
$\begingroup$

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.

$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$