$\sum_{n=1}^{\infty}\sum_{i=nr}^{\infty}f(i)=\sum_{i=r}^{\infty}\sum_{n=1}^{\left\lfloor \frac{i}{r}\right\rfloor}f(i)$

Question

This was given as part of the answer of a more complex problem:

$$\sum_{n=1}^{\infty}\sum_{i=nr}^{\infty}f(i)=\sum_{i=r}^{\infty}\sum_{n=1}^{\left\lfloor \frac{i}{r}\right\rfloor}f(i)=\sum_{i=r}^{\infty}\left\lfloor\frac{i}{r}\right\rfloor f(i)$$

But I don't understand how the above follows.

So I expanded the first expression $$\sum_{n=1}^{\infty}\sum_{i=nr}^{\infty}f(i)=\sum_{n=1}^{\infty}f(nr)+f(nr+1)+\dots$$

$$=\big(f(r)+f(r+1)+\dots\big)+\big(f(2r)+f(2r+1)+\dots\big)+\dots$$

And don't see how I can continue here.

How is the floor function related to the above expression?

Answer 1

Lets start from where you were lost: \begin{align} \sum_{n=1}^{\infty}\sum_{i=nr}^{\infty} f(i) = \underset{n=1}{\underbrace{f(r)+f(r+1)+\ldots}} + \underset{n=2}{\underbrace{f(2r)+f(2r+1)+\ldots}} + \underset{n=3}{\underbrace{f(3r)+f(3r+1)+\ldots}} +\ldots. \end{align} Clearly, $f(r),f(r+1),\ldots,f(2r-1)$ appears only once in the summation, as those terms appear only when $n=1$, and not for other values of $n$. $f(2r),f(2r+1),\ldots,f(3r-1)$ appears only twice in the summation, as those terms appear only when $n=1,2$, and not for other values of $n$.

More generally, $f(nr),f(nr+1),\ldots,f((n+1)r-1)$ appears $n$ times in the summation. Therefore, $f(i)$ appears $\lfloor\frac{i}{r}\rfloor$ times as $\lfloor\frac{nr}{r}\rfloor=\lfloor\frac{nr+1}{r}\rfloor=\ldots=\lfloor\frac{(n+1)r-1}{r}\rfloor=n$.

Hence,

\begin{equation} \sum_{n=1}^{\infty}\sum_{i=nr}^{\infty} f(i) =\sum_{i=r}^{\infty} \lfloor\frac{i}{r}\rfloor f(i). \end{equation}

Answer 2

This technique is sometimes called double-counting, especially when the sums are finite. Assuming that Fubini's theorem is applicable, we have

\begin{align*} \sum_{n=1}^{\infty}\sum_{i=nr}^{\infty} f(i) = \sum_{\substack{i, n \geq 1 \\ i \geq nr}} f(i) = \sum_{\substack{i, n \geq 1 \\ n \leq i/r}} f(i) = \sum_{i=1}^{\infty} \sum_{n \, : \, 1\leq n \leq i/r} f(i). \end{align*}

In the last expression, $f(i)$ is independent of $n$. So the value of the sum is simply $f(i)$ times the number of summands, which is exactly $\lfloor i/r \rfloor$, i.e.,

$$ \sum_{n \, : \, n \leq i/r} f(i) = (\#\{n : 1\leq n \leq i/r \}) f(i) = \left\lfloor\frac{i}{r}\right\rfloor f(i). $$

Therefore the desired identity follows.

Here is a way of visualizing the situation. For the sum $\sum_{n=1}^{\infty} \sum_{i=nr}^{\infty} a_{n,i}$, we represent the term $a_{n,i}$ as the dot at $(n, i)$. Then the range of this double sum can be visualized as:

The above figure corresponds to $r = \sqrt{2}$. Then $\sum_{n=1}^{\infty} \sum_{i=nr}^{\infty} a_{n,i}$ amounts to summing over each column first. If we sum over each row first, then the bound of $n$ for the '$i$-th row' is determined by the inequality $i \geq nr$, or equivalently, $n \leq i/r$. Since $n$ only takes integer values, this is equivalent to $n \leq \lfloor i/r \rfloor$, hence the identity

$$ \sum_{n=1}^{\infty} \sum_{i=nr}^{\infty} a_{n,i} = \sum_{i=1}^{\infty} \sum_{n=1}^{\lfloor i/r \rfloor} a_{n,i} $$

follows under suitable condition on $a_{n,i}$.