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$