## A Combinatorial Proof of a Formula Involving Euler’s Totient Function

Several years ago I found a proof of the following identity, which I had not seen before (and still haven’t seen anywhere else):

$\displaystyle \sum_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{n(n+1)}{2},$

where $\varphi(n)$ is Euler’s totient function, the number of positive integers less than or equal to $n$ and relatively prime to $n$.

Over a year ago I asked for additional proofs of this identity on Math Stack Exchange and got some nice ones.  My favorite, though, is a combinatorial proof that I managed to come up with after I had asked the question.  (It was a modification of one of my original proofs.)

Proof: Both sides count the number of fractions (reducible or irreducible) in the interval $(0,1]$ with denominator $n$ or smaller.

Right side: the number of ways to pick a numerator and a denominator is the number of ways to choose two numbers with replacement from the set $\{1, 2, \ldots, n\}$.  This is known to be
$\displaystyle \binom{n+2-1}{2} = \frac{n(n+1)}{2}.$

Left side: The number of irreducible fractions in $(0,1]$ with denominator $k$ is equal to the number of positive integers less than or equal to $k$ and relatively prime to $k$; i.e., $\varphi(k)$.  For a given irreducible fraction $\frac{a}{k}$, there are $\left\lfloor \frac{n}{k} \right\rfloor$ total fractions with denominators $n$ or smaller in its equivalence class.  (For example, if $n = 20$ and $\frac{a}{k} = \frac{1}{6}$, then the fractions $\frac{1}{6}, \frac{2}{12}$, and $\frac{3}{18}$ are those in its equivalence class.)  Thus the sum
$\displaystyle \sum_{k=1}^n \left\lfloor\frac{n}{k} \right\rfloor \varphi (k)$
also gives the desired quantity.

This identity comes from the more general setting of summing a multiplicative function convoluted with the constant function, that is $1*f(n)=\sum_{d|n} f(d)$ where * represents Dirichlet convolution. Looking at the sum $\sum_{n\leq x}1*f(n)=\sum_{n\leq x}\sum_{d|n} f(d)$, we see that by switching the order of summation, the above equals $\sum_{d\leq x} f(d)\sum_{n\leq x:\ d|n}1=\sum_{d\leq x} f(d) \left[\frac{x}{d}\right]$. Since $\sum_{d|n}\phi(d)=n$, and $\sum_{n\leq x} n =\frac{x(x+1)}{2}$, we recover your identity $\frac{x(x+1)}{2}=\sum_{n\leq x }\phi(n) \left[\frac{x}{n}\right]$.