how to prove the relation between the floor function and the number of divisors

Question

I am trying to get an intuitive meaning (a proof) or why the following is true. $$\sum_{k = 1}^n \sum_{d|k} 1 = \sum_{d = 1}^n \left[\frac{n}{d} \right]$$

I know that $f(x) = [x] = \sum_{n \leq x} 1$ but I can't see it in the case of a fraction.

Edit: can someone please tell me what I am doing wrong. I believe its something to do with summations. I know the divisor function $\tau(k) = \sum_{d|k} 1 $ so consider $$\sum_{n \leq x} \tau(n) = \sum_{n \leq x}\sum_{d|n} 1 = \sum_{n \leq x} \left[ \frac{x}{n} \right]$$ so this must mean $$\sum_{d|n} 1 = \left[ \frac{x}{n} \right]$$ which is clearly false. So what am I missing?

Answer 1

Consider first $$\sum_{k=1}^n \sum_{d|k} 1$$

Here is a table

k | divisors of k
--------------------
n |
..| ...
9 | 1   3           9
8 | 1 2   4       8
7 | 1           7
6 | 1 2 3     6
5 | 1       5
4 | 1 2   4
3 | 1   3
2 | 1 2
1 | 1

The sum is just going up the rows of this table counting the number of divisors: how many things appear in that row.

Now think about counting the same thing the other way, so you're thinking about the sum over columns: How many times does each divisor divide the numbers below n.

2 occurs as a divisor of half the numbers below n, 3 occurs as a divisor for 1/3 of them and so on..

This gives $$\sum_{d=1}^n \left[\frac{n}{d}\right]$$

Answer 2

For each positive integer $d\le n$ there are $\left\lfloor\dfrac{n}d\right\rfloor$ multiples of $d$ in the set $\{1,2,\dots,n\}$. Use this fact to reverse the order of summation:

$$\begin{align*} \sum_{k=1}^n\sum_{d\mid k}1&=\sum_{d=1}^n\sum_{k\text{ is a multiple of }d}1\\\\ &=\sum_{d=1}^n\left\lfloor\frac{n}d\right\rfloor\;. \end{align*}$$