Let φ(n) be Euler’s totient function, the number of positive integers less than or equal to n and relatively prime to n.
I have two proofs, one of which is partially combinatorial.
I’m posing this problem partly because I think some folks on this site would be interested in working on it and partly because I would like to see a purely combinatorial proof. (But please post any proofs; I would be interested in noncombinatorial ones, too. I’ve learned a lot on this site by reading alternative proofs of results I already know.)
I’ll wait a few days to give others a chance to respond before posting my proofs.
EDIT: The two proofs in full are now given among the answers.
One approach is to use the formula ∑d∣kφ(d)=k
So we have that n∑k=1∑d∣kφ(d)=n(n+1)/2
Exchanging the order of summation we see that the φ(d) term appears ⌊nd⌋ times
Or in other words, if we have the n×n matrix A such that
A[i,j]=φ(j) if j∣i and 0 otherwise.
The sum of elements in row i is i.
The sum of elements in column j is ⌊nj⌋φ(j) and the identity just says the total sum by summing the rows is same as the total sum by summing the columns.