Let φ(n) be Euler’s totient function, the number of positive integers less than or equal to n and relatively prime to n.

Challenge: Prove

n∑k=1⌊nk⌋φ(k)=n(n+1)2.

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.

**Answer**

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

and thus

n∑d=1⌊nd⌋φ(d)=n(n+1)/2

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.

**Attribution***Source : Link , Question Author : Mike Spivey , Answer Author : J. M. ain’t a mathematician*