# $\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)$

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?

• Since $n$ is an integer, the inequality $i \geq nr$ is equivalent to $n \leq \frac i r$ which is equivalent to $n \leq [\frac i r]$. – Kavi Rama Murthy Apr 15 at 5:21
• Try writing out the terms in your expansion for $r=1,\,r=2,\,r=3$. – John Wayland Bales Apr 15 at 5:29

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,

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

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