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?
Justifying $\sum\limits_{n\leq x}d(n)=\sum\limits_{a\leq x}\left[\frac{x}{a}\right]$
-
0I would try to write all the sums using characteristic functions. – 2012-12-10
2 Answers
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$.
-
0Perfect, this was exactly what I was looking for! – 2012-12-10
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.