Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

2 Answers 2

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|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.