Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Regarding your "Edit". It's not true that if the sum of F is equal to the sum of G, then F = G. – user58512 Mar 23 '13 at 1:51
I see. Thank you. – Tyler Hilton Mar 23 '13 at 1:53
up vote 1 down vote accepted

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

share|cite|improve this answer
Is 1 not a divisor? – Tyler Hilton Mar 23 '13 at 1:58
it is, it should be in the table too. I 've added it. – user58512 Mar 23 '13 at 2:05

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.