1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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]$. $\endgroup$ – Kavi Rama Murthy Apr 15 at 5:21
  • $\begingroup$ Try writing out the terms in your expansion for $r=1,\,r=2,\,r=3$. $\endgroup$ – John Wayland Bales Apr 15 at 5:29
1
$\begingroup$

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}

$\endgroup$
1
$\begingroup$

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:

1

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.