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.

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

2 Answers

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|improve this answer
    
Perfect, this was exactly what I was looking for! –  Carolus Dec 10 '12 at 15:45
add comment

Hint:

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|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.