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}$

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.

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.

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.