Identity involving Euler’s totient function: n∑k=1⌊nk⌋φ(k)=n(n+1)2\sum \limits_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{n(n+1)}{2}

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

nk=1nkφ(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 dkφ(d)=k

So we have that nk=1dkφ(d)=n(n+1)/2

Exchanging the order of summation we see that the φ(d) term appears nd times

and thus

nd=1ndφ(d)=n(n+1)/2

Or in other words, if we have the n×n matrix A such that

A[i,j]=φ(j) if ji 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

Leave a Comment