Summation identity involving the floor function (Kömal November B. 4666)
Prove that $\sum_{k=1}^n (2k-1) [\frac{n}{k}]=\sum_{k=1}^n [\frac{n}{k}]^2$ for every positive integer $n$, where $[n]$ is the largest integer greater than or equal to $n$. 
 A: The trick here is to introduce a second summation and then reverse the order of summation. Introducing the second summation is easy:
$$\sum_{k=1}^n(2k-1)\left\lfloor\frac{n}k\right\rfloor=\sum_{k=1}^n(2k-1)\sum_{j=1}^{\lfloor n/k\rfloor}1=\sum_{k=1}^n\sum_{j=1}^{\lfloor n/k\rfloor}(2k-1)\;.\tag{1}$$
Reversing the order of summation is a little trickier than usual. Since $\left\lfloor\frac{n}1\right\rfloor=n$, it’s clear that we want the outer sum to be $\sum_{j=1}^n$; the trick is to get the inner sum to catch exactly the values of $k$ for which $\left\lfloor\frac{n}k\right\rfloor\ge j$. Since we’re talking about positive integers, $\left\lfloor\frac{n}k\right\rfloor\ge j$ iff $n\ge kj$ iff $\left\lfloor\frac{n}j\right\rfloor\ge k$, so
$$\sum_{k=1}^n\sum_{j=1}^{\lfloor n/k\rfloor}(2k-1)=\sum_{j=1}^n\sum_{k=1}^{\lfloor n/j\rfloor}(2k-1)=\sum_{j=1}^n\left\lfloor\frac{n}j\right\rfloor^2\;,\tag{2}$$
since the sum of the first $m$ odd positive integers is $m^2$.
Added: To get a more intuitive idea of where the trick comes from, consider the case $n=8$, say:
$$\begin{array}{rccc}
k:&1&2&3&4&5&6&7&8\\
2k-1:&1&3&5&7&9&11&13&15\\
\lfloor 8/k\rfloor:&8&4&2&2&1&1&1&1
\end{array}$$
Now think of the bottom line as giving a frequency count for the entry in the line $2k-1$ line, and replace it with that many copies of the corresponding $2k-1$ entry:
$$\begin{array}{rccc}
k:&1&2&3&4&5&6&7&8\\
2k-1:&1&3&5&7&9&11&13&15\\
\lfloor 8/k\rfloor:&8&4&2&2&1&1&1&1\\ \hline
&1&3&5&7&9&11&13&15\\
&1&3&5&7\\
&1&3\\
&1&3\\
&1\\
&1\\
&1\\
&1\\
\end{array}$$
The sum $(1)$ corresponds to summing the columns below the line and then adding those sums. Reversing the order of summation as in $(2)$ corresponds to summing the rows below the line and then adding those sums.
