Identity involving Euler's totient function: $\sum \limits_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{n(n+1)}{2}$

Question

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

Challenge: Prove

$$\sum_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{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 1

One approach is to use the formula $\displaystyle \sum_{d \mid k} \varphi(d) = k$

So we have that $\displaystyle \sum_{k=1}^{n} \sum_{d \mid k} \varphi(d) = n(n+1)/2$

Exchanging the order of summation we see that the $\displaystyle \varphi(d)$ term appears $\displaystyle \left\lfloor \frac{n}{d} \right\rfloor$ times

and thus

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

Or in other words, if we have the $n \times n$ matrix $A$ such that

$\displaystyle A[i,j] = \varphi(j)$ if $j \mid i$ and $0$ otherwise.

The sum of elements in row $i$ is $i$.

The sum of elements in column $j$ is $\displaystyle \left\lfloor \frac{n}{j} \right\rfloor \varphi(j)$ and the identity just says the total sum by summing the rows is same as the total sum by summing the columns.

Answer 2

We can use induction.

We have $ \lfloor (n+1)/k \rfloor - \lfloor n/k \rfloor = 1 $ when $n \equiv -1 \textrm{ mod } k,$ (for $k>1$) and $0$ otherwise. Hence

$$ \phi(1) + \sum_{k=2}^n \left( \left\lfloor \frac{n+1}{k} \right\rfloor -
\left\lfloor \frac{n}{k} \right\rfloor \right) \phi(k) = \sum_{k=1, k \textrm{ s.t. } n \equiv -1 \textrm{ mod } k}^n \phi(k)$$ $$= \sum_{ k | (n+1), k \ne n+1} \phi(k) = (n+1) - \phi(n+1),$$

using $\sum_{d|k} \phi(d) = k.$ So assuming the result is true for $n,$ we have

$$\sum_{k=1}^{n+1} \left\lfloor \frac{n+1}{k} \right\rfloor \phi(k) = \phi(n+1) + \sum_{k=1}^n \left( \left\lfloor \frac{n+1}{k} \right\rfloor -
\left\lfloor \frac{n}{k} \right\rfloor \right) \phi(k) + \frac{n(n+1)}{2}$$

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

which, using the previous result to substitute for the summation,

$$= (n+1) + \frac{n(n+1)}{2} = \frac{(n+1)(n+2)}{2}.$$

Noting that the result is true when $n=1 \textrm{ and } 2$ completes the proof.

Answer 3

Look at the problem of counting all the triples (d,m+1,k) where $d\leq m\leq n$ and $gcd(d,m)=\frac{m}{k}$. For each (d,m+1) we have exactly one k such that $gcd(d,m)=\frac{m}{k}$, and so we are counting exactly all the pairs (i,j) where $ i < j \leq n+1 $ which is $\binom{n+1}{2}$.

On the other hand, for each k , if $ gcd(d,m)=\frac{m}{k} $, then $ k \mid m $ and there are $ \left\lfloor \frac{n}{k}\right\rfloor $ such m's, and for each m we have $\varphi(k)$ d's that satisfies this equality, so there are $ \left\lfloor \frac{n}{k}\right\rfloor \varphi(k) $ triples that end with k.

---

The idea is counting the number of ways to choose two numbers from 1,2,...,n+1 (which is the right side of the equation). Once you choose the larger number m+1, you have m options which is exactly $\sum_{d\mid m} \varphi(d)$ (this is basically what Moron wrote). What I wanted to do is to change the counting according to the "relation" between d and m, and the one that worked out is that $\frac{m}{gcd(d,m)}=k$.

So, going over triples (d,m+1,k) where $\frac{m}{gcd(d,m)}=k$ and $d\leq m\leq n$ just mean that (d,m+1) is an ordered pair from {1,...,n} and k is decided as above.

On the other hand, for specific k, if $\frac{m}{gcd(d,m)}=k$ then $k \mid m$ and there are $ \left\lfloor \frac{n}{k}\right\rfloor$ such m's. For each m, if $gcd(d,m)=m/k$ then $gcd(\frac{d}{m/k},\frac{m}{m/k})=gcd(\frac{d}{m}k,k)=1$ and there are $\varphi(k)$ such d's (because $d\leq m$).

So, or each k there are $ \left\lfloor \frac{n}{k}\right\rfloor \varphi(k) $ options , and summing over k will give the left side of the equation.

Answer 4

In case anyone is interested, here are the full versions of my two proofs. (I constructed the combinatorial one from my original partially combinatorial one after I posted the question.)

---

The non-combinatorial proof

As Derek Jennings observes, $\lfloor \frac{n+1}{k} \rfloor - \lfloor \frac{n}{k} \rfloor$ is $1$ if $k|(n+1)$ and $0$ otherwise. Thus, if $$f(n) = \sum_{k=1}^n \left\lfloor\frac{n}{k} \right\rfloor \varphi (k),$$ then $$\Delta f(n) = f(n+1) - f(n) = \sum_{k|(n+1)} \phi(k) = n+1,$$ where the last equality follows from the well-known formula Aryabhata cites.

Then $$\sum_{k=1}^n \left\lfloor\frac{n}{k} \right\rfloor \varphi (k) = f(n) = \sum_{k=0}^{n-1} \Delta f(k) = \sum_{k=0}^{n-1} (k+1) = \frac{n(n+1)}{2}.$$

---

The combinatorial proof

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

For the 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 $$\binom{n+2-1}{2} = \frac{n(n+1)}{2}.$$

Now for the 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)$. Then, 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 $$\sum_{k=1}^n \left\lfloor\frac{n}{k} \right\rfloor \varphi (k)$$ also gives the desired quantity.