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

In a proof of the average order of $d(n)$, the number of divisors of $n$, I saw the following line: $$\sum_{n\leq x}d(n)=\sum_{ab\leq x}1=\sum_{a\leq x}\left[\frac{x}{a}\right].$$ I have a hard time seeing exactly what's going on. How can we justify these manipulations?

share|cite|improve this question
What's the definition of $d(n)$? – Cantor Dec 10 '12 at 15:16
@Cantor: $d(n)$ is the number of divisors of $n$. – Carolus Dec 10 '12 at 15:19
I would try to write all the sums using characteristic functions. – Cantor Dec 10 '12 at 15:32
up vote 4 down vote accepted

We can write

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

because $a\mid n$ is equivalent to $n=ab$ for precisely one positive integer $b$ (namely $b=n/a$). The number of divisors of $n$ is equal to the number of pairs of positive integers $a,b$ such that $n=ab$.

Since $ab\le x\iff b\le x/a$, we can write

$$\sum_{ab\le x}1=\sum_{b\le x/a}1=\sum_a \left\lfloor\frac{x}{a}\right\rfloor.$$

Note that in the middle sum, both $a$ and $b$ are varying, but a $1$ is counted in only when $b\le x/a$, and the number of integers $b$ such $b\le x/a$ is given by the floor function $\lfloor x/a\rfloor$.

share|cite|improve this answer
Perfect, this was exactly what I was looking for! – Carolus Dec 10 '12 at 15:45


Write $$d(n)=\sum_{j=1}^\infty \chi_{\{n/j\in \mathbb{N}\}}(j)$$

$$\sum_{n\leq x}d(n)= \sum_{k=1}^\infty \chi_{\{k \leq x\}}(k) d(k) = \sum_{k=1}^\infty \chi_{\{k \leq x\}}(k)\sum_{j=1}^\infty \chi_{\{n/j\in \mathbb{N}\}}(j)$$

Now interchange the sums using Fubini and you have your result. Note that all sums are finite.

Characteristic function of a set $\chi_A(j)$ is defined to be $1$ if $j\in A$ and zero otherwise. It is useful to write sums and integrals using characteristic functions of their domains because then you can deal with sums and integrals that have the same domain and you can interchange sums (or integrals) if you have more than one using Fubini.

anon's answer is good, I'm just writing this because it is a useful trick.

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.