On a multisection of a series

Question

Let $x$ be a real number and $\lfloor{x}\rfloor$ denote the greatest integer less than or equal to $x$. Let $r$ be a positive integer. Let $a$ and $n$ be nonnegative integers such that $n-a+1\geq r$. Prove that

$$ \sum_{k=a}^{n} f(k) = \sum_{j=0}^{r-1} \sum_{k=\lfloor{\frac{a+r-1-j}{r}}\rfloor}^{\lfloor{\frac{n-j}{r}}\rfloor} f(rk+j).$$

I couldn't arrive at any proof.

Also it is noted that for a fixed $r$, this identity partitions the sum modulo remainder classes. The number of remainder classes is indexed by $j$. Could you explain this note?

I generally have trouble with series whose indices involves greatest integer function, are there any fast techniques to solve them?

Answer 1

Let $m$ be an integer, note that there exists a $k\in\mathbb{N}$ and a $0\leq j\leq r-1$ such that $m=rk+j$, where $j$ is the remainder of $m$ divided by $r$. We also say that $m$ is $j$ modulo $r$. In the sum above what happens is we fix $j$ and then run through all $k$ such that $a\leq rk+j\leq n$. This gives the sum modulo a remainder class. Adding all the remainder classes then gives you the total sum.

To right down the identity all you have to figure out are the correct bounds for $k$. So let $0\leq j\leq r-1$. We have to solve $$a\leq rk+j\leq n\Leftrightarrow \frac{a-j}{r}\leq k\leq \frac{n-j}{r}$$ So the upper bound of $k$ if $\lfloor\frac{n-j}{r}\rfloor$, i.e. the biggest integer smaller than \frac{n-j}{r}. With the same reasoning the lower bound is given by $\lceil\frac{a-j}{r}\rceil$, however as they require the lower bound it requires a bit more thinking.

Now suppose $a=sr+t$ with $s\in\mathbb{N}$ and $0\leq t\leq r-1$, then $$\lceil\frac{a-j}{r}\rceil=\left\lceil\frac{sr+t-j}{r}\right\rceil=\begin{cases}s&\text{ if }t-j\leq0\\s+1&\text{ if }t-j>0\end{cases}.$$ However since we have to use the lower bound we have to convert this. Instinctively you might think to use $\lfloor\frac{a+r-j}{r}\rfloor$, but then we have $$\lfloor\frac{a+r-j}{r}\rfloor=\left\lfloor\frac{(s+1)r+t-j}{r}\right\rfloor=\begin{cases}s&\text{ if }t-j<0\\s+1&\text{ if }t-j\geq0\end{cases},$$ i.e. it goes wrong for $t-j=0$ when $a-j$ is an integer. Hence we use $\lfloor\frac{a+r-1-j}{r}\rfloor$ to get the desired result. (Note that for the worst case scenario $t=0$ and $j=r-1$ we have $\frac{a+r-1-j}{r}=\frac{sr+r-1-r+1}{r}=\frac{sr}{r}=s$ as required.)

So the sum of the elements of the remainder class of some $0\leq j\leq r-1$ between $a$ and $n$ is given by $$\sum_{k=\left\lfloor\frac{a+r-1-j}{r}\right\rfloor}^{\lfloor\frac{n-j}{r}\rfloor}f(rk+j)$$ and the total sum is given by the sum of the sums of remainder classes $$\sum^{n}_{i=a}f(i)=\sum^{r-1}_{j=1}\sum_{k=\left\lfloor\frac{a+r-1-j}{r}\right\rfloor}^{\lfloor\frac{n-j}{r}\rfloor}f(rk+j).$$

I hope this helps, let me know if a part is still unclear.

Answer 2

Any integer $k$ can be represented as $i r + j$ with $0 \leq j < r$. The condition $a \leq k \leq n$ gives $(a - j)/r \leq i \leq (n - j)/r$. Therefore, $$\sum_{k = a}^n f(k) = \sum_{j = 0}^{r - 1} \sum_{i = \lceil \frac {a - j} r \rceil}^{\lfloor \frac {n - j} r \rfloor} f(i r + j).$$ We need to show that $$\left \lceil \frac m r \right \rceil = \left \lfloor \frac m r - \frac 1 r \right \rfloor + 1, \quad m = a - j.$$ If $m/r$ is an integer, then, since $0 < 1/r \leq 1$, we have $\lfloor m/r - 1/r \rfloor = m/r - 1$.

If $m/r$ isn't an integer, it is greater than $\lfloor m/r \rfloor$ by at least $1/r$, therefore $\lfloor m/r - 1/r \rfloor = \lfloor m/r \rfloor$, and $\lceil x \rceil = \lfloor x \rfloor + 1$ for $x \not \in \mathbb Z$.

We can see that $1/r$ in the lower limit of the sum can be replaced by any other value in the interval $(0, 1/r]$. Also, the condition $n - a + 1 \geq r$ is redundant, the only requirement is $r > 0$.

Answer 3

First, $$ \sum_{k=a}^{n} f(k) = \sum_{i=a}^{n} f(i).\tag1$$ Therefore, calculates sum of the sequence $\{f(i)\},$ where index $i$ changes from $a$ to $n.$

Integer division of $i$ to the given integer positive $r$ presents index $i$ in the form of $$i=kr+j,$$ where $j$ is reminder and $k$ is quotent.

The reminder can change from $0$ to $r-1.$

If reminder $j$ is given, then maximal possible value of quotent is $\left\lfloor\dfrac{n-j}r\right\rfloor$
and minimal possible value of quotent is $$\left\lfloor\dfrac{a-j-1}r\right\rfloor+1 = \left\lfloor\dfrac{a+r-j-1}r\right\rfloor.$$

Thus, $$ \sum_{i=a}^{n} f(i) = \sum_{j=0}^{r-1} \sum_{\large k=\lfloor{\frac{a+r-1-j}{r}}\rfloor}^{\large\lfloor{\frac{n-j}{r}}\rfloor} f(rk+j).$$

Taking in account $(1),$ this elaborates the issue identity.

Answer 4

This is an answer based on series manipulation. In order to ease things we make a two-step approach. At first we show the identity is valid in case $a=0$ and then the generalisation for integral $a\geq 0$ follows easily.

Step 1: $a=0$

The following is valid for integral $1\leq r\leq n$:

\begin{align*} \sum_{k=0}^nf(k)=\sum_{j=0}^{r-1}\sum_{k=0}^{\left\lfloor\frac{n-j}{r}\right\rfloor}f(rk+j)\tag{1} \end{align*}

Observe the simple lower limit $k=0$ of the inner sum. Setting $a=0$ we have \begin{align*} \left\lfloor\frac{a+r-1-j}{r}\right\rfloor=\left\lfloor\frac{r-1-j}{r}\right\rfloor=0 \end{align*} since $0\leq \frac{r-1-j}{r}<1$ if $0\leq j<r$.

At first we consider (1) when $n$ is an integer multiple of $r$. In this case we see \begin{align*} \sum_{k=0}^nf(k)&=\sum_{k=0}^{\frac{n}{r}-1}\sum_{j=0}^{r-1}f(rk+j)+f(n)\\ &=\sum_{j=0}^{r-1}\sum_{k=0}^{\frac{n}{r}-1}f(rk+j)+f(n)\tag{2} \end{align*} The multisection in (2) corresponds to a partitioning of $[0,n]\cap\mathbb{Z}$ into $r$ equally sized, right half-open intervals $$[rk,rk+r)\cap\mathbb{Z}, \qquad\qquad 0\leq k<\frac{n}{r}$$ of length $\frac{n}{r}$ together with the right-most point $\{n\}$.

Now we consider $0\leq r\leq n$. In this more general setting we have \begin{align*} n=r\left\lfloor\frac{n}{r}\right\rfloor+l\qquad\qquad 0\leq l <\left\lfloor\frac{n}{r}\right\rfloor\tag{3} \end{align*}

We obtain from (2) and (3) \begin{align*} \color{blue}{\sum_{k=0}^n f(k)}&=\sum_{j=0}^{r-1}\sum_{k=0}^{\left\lfloor\frac{n}{r}\right\rfloor-1}f(rk+j) +\sum_{j=0}^l f\left(r\left\lfloor\frac{n}{r}\right\rfloor+j\right)\tag{4}\\ &=\sum_{j=0}^{l}\sum_{k=0}^{\left\lfloor\frac{n}{r}\right\rfloor}f(rk+j) +\sum_{j=l+1}^{r-1}\sum_{k=0}^{\left\lfloor\frac{n}{r}\right\rfloor-1}f(rk+j)\tag{5}\\ &=\sum_{j=0}^{r-1}\,\,\ \sum_{k=0}^{\left\lfloor\frac{n}{r}\right\rfloor+\left\lfloor\frac{l-j}{r}\right\rfloor}f(rk+j)\tag{6}\\ &=\sum_{j=0}^{r-1}\sum_{k=0}^{\left\lfloor\frac{r\lfloor n/r\rfloor +l-j}{r}\right\rfloor} f(rk+j)\tag{7}\\ &\,\,\color{blue}{=\sum_{j=0}^{r-1}\sum_{k=0}^{\left\lfloor\frac{n-j}{r}\right\rfloor} f(rk+j)}\tag{8}\\ \end{align*} and the claim (1) follows.

Comment:

• In (4) we use $\left\lfloor\frac{n}{r}\right\rfloor$ instead of $\frac{n}{r}$ and instead of the single value $f(n)$ we have now to consider a sum ranging over $0\leq j\leq l$ according to (3) resulting in the right-hand sum.

• In (5) we split the left-hand of (4) into two double sums with index region $0\leq j\leq l$ and $l<j\leq r-1$. This way we can merge the right-hand sum of (4) into the left-hand sum. Note the upper limit of the inner sum from the left-hand sum is $\left\lfloor\frac{n}{r}\right\rfloor$ (and no longer $\left\lfloor\frac{n}{r}\right\rfloor-1$).

• In (6) we collect both double sums of (5) into one double sum with a small trick. We add \begin{align*} \left\lfloor\frac{l-j}{r}\right\rfloor= \begin{cases} 0&\quad 0\leq j\leq l\\ -1&\quad l< j\leq r-1 \end{cases} \end{align*}

• In (7) we observe $m:=\left\lfloor\frac{n}{r}\right\rfloor$ is an integer and we use the identity $$m+\left\lfloor\frac{l-j}{r}\right\rfloor=\left\lfloor\frac{rm+l-j}{r}\right\rfloor.$$

• In (8) we use $n=r\left\lfloor\frac{n}{r}\right\rfloor+l$ from (3).

Step 2: $a\geq 0$

We obtain from (8) \begin{align*} \color{blue}{\sum_{k=a}^nf(k)} &=\sum_{k=0}^n f(k)-\sum_{k=0}^{a-1} f(k)\\ &=\sum_{j=0}^{r-1}\sum_{k=0}^{\left\lfloor\frac{n-j}{r}\right\rfloor} f(rk+j) -\sum_{j=0}^{r-1}\sum_{k=0}^{\left\lfloor\frac{a-1-j}{r}\right\rfloor} f(rk+j)\\ &=\sum_{j=0}^{r-1}\ \sum_{k=\left\lfloor\frac{a-1-j}{r}\right\rfloor+1}^{\left\lfloor\frac{n-j}{r}\right\rfloor} f(rk+j)\\ &\,\,\color{blue}{=\sum_{j=0}^{r-1}\ \sum_{k=\left\lfloor\frac{a+r-1-j}{r}\right\rfloor}^{\left\lfloor\frac{n-j}{r}\right\rfloor} f(rk+j)}\\ \end{align*}

and OPs claim follows.