How to show $\sum_{n\leq x}d(n)=\sum_{ab\leq x}1$?

45 Views Asked by At

How to show this equation below is true.

$$\sum_{n\leq x}d(n)=\sum_{ab\leq x}1$$

$d(n)$ is the divisior function. It seems easy but i just can't see it.

2

There are 2 best solutions below

0
On BEST ANSWER

Just modify the sums slowly, for example from right to left:

$$\sum_{ab\le x} 1 = \sum_{n\le x} \sum_{ab=n} 1 = \sum_{n\le x} \sum_{a \mid n} 1 =\sum_{n\le x} d(n).$$

0
On

Let $X=\{(a,b)\mid ab\leq x\}$, let $X_n=\{(a,b)\mid ab=n\}$.

Show that $$X=\bigcup_{n\leq x} X_n$$ and that the $X_n$ are disjoint.

Then the right hand side is $|X|$ and the left hand side is $\sum_{x\leq n} |X_n|.$