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}$ 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.
 A: Look at the problem of counting all the triples $(d,m+1,k)$ where $d\leq m\leq n$ and $\gcd(d,m)=\dfrac{m}{k}$.
For each $(d,m+1)$ we have exactly one k such that $\gcd(d,m)=\dfrac{m}{k}$, and so we are counting exactly all the pairs $(i,j)$  where $ i < j \leq n+1 $ which is $\dbinom{n+1}{2}$.
On the other hand, for each k , if $ \gcd(d,m)=\dfrac{m}{k} $, then $ k \mid m $ and there are $ \left\lfloor \dfrac{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 \dfrac{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,\ldots,(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 $\displaystyle \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 $\dfrac{m}{\gcd(d,m)}=k$.
So, going over triples $(d,m+1,k)$ where $\dfrac{m}{\gcd(d,m)}=k$ and $d\leq m\leq n$ just mean that $(d,m+1)$ is an ordered pair from $\{1,\ldots,n\}$ and $k$ is decided as above.
On the other hand, for specific $k$, if $\dfrac{m}{\gcd(d,m)}=k$ then $k \mid m$ and there are $ \left\lfloor \dfrac{n}{k}\right\rfloor$ such $m$'s. For each $m$, if $\gcd(d,m)=\dfrac{m}{k}$ then $\gcd \left(\dfrac{d}{\frac{m}{k}},\dfrac{m}{\frac{m}{k}}\right)= \gcd \left(\dfrac{dk}{m},k \right)=1$ and there are $\varphi(k)$ such $d$'s (because $d\leq m$).
So, for each k there are $ \left\lfloor \dfrac{n}{k}\right\rfloor \varphi(k) $ options , and summing over $k$ will give the left side of the equation. $\square$
A: 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.
A: 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.
A: 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.
