TITLE: On swapping the order of a summation
QUESTION [4 upvotes]: Consider the following sum $$S=\sum_{k=1}^nd(k)$$
where $d(k)$ is the number of divisors of $k$. We can rewrite the sum like this $$S=\sum_{k=1}^n\sum_{d\mid k}^k1$$
but now how can I change the order of summation? we know $d\mid k$ and $k\le n \implies d\le n$. Now what? I'm generaly bad at swapping summations

REPLY [0 votes]: Here we change the order of summation by transformations of the sums only.

We obtain
\begin{align*}
\color{blue}{\sum_{k=1}^nd(k)}&=\sum_{k=1}^n\sum_{{d=1}\atop{d\mid k}}^k1
=\sum_{{1\leq d\leq k\leq n}\atop {d\mid k}}1\tag{1}\\
&=\sum_{d=1}^n\sum_{{k=d}\atop{d\mid k}}^n 1\tag{2}\\
&=\sum_{d=1}^n\sum_{{k=d}\atop {dd^{\prime}=k}}^n1\tag{3}\\
&=\sum_{d=1}^n\sum_{d^{\prime}=1}^{\left\lfloor n/d\right\rfloor} 1\tag{4}\\
&\,\,\color{blue}{=\sum_{d=1}^n\left\lfloor\frac{n}{d}\right\rfloor}\tag{5}
\end{align*}

Comment:

In (1) we write the index range somewhat more conveniently.

In (2) we change the order of summation.

In (3) we introduce $d^\prime$ using the definition of the divisor $d$.

In (4) we sum over $d^\prime$ instead of $k$. We observe $d^\prime=1$ if $k=d$, $d^\prime=2$ if $k=2d$, etc.

In (5) we make a final simplification.


This is a special case of the following identity
\begin{align*}
\color{blue}{\sum_{k=1}^n\sum_{d\mid k}f(d,k)=\sum_{d=1}^n\sum_{k=1}^{\left\lfloor n/d\right\rfloor}f(d,kd)}
\end{align*}
which is shown in this answer.
{"set_name": "stack_exchange", "score": 4, "question_id": 4440939}