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

Solution 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.

Solution 2:

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.

Solution 3:

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.