Supposing $b > 1$ and $x \geq 1$, the pseudocode algorithm
L := 0
while x >= b do
L := L + 1
x := x / b
end do
return L
returns $\lfloor \log_b x \rfloor$. (CS aside: If $b$ is an integer, this gives an exact result when all variables have type int
. If the variables have type, e.g., float
, possibly this algorithm can suffer from rounding errors.) For any $x$ the while loop is run $\lfloor \log_b x \rfloor + 1$ times, so this algorithm has complexity $O(\log x)$ in $x$.
The index of summation is ranging as
$$
a \le k \le n
$$
Replace it with its even and odd components
$$
k = 2j - i\quad \left| {\,i = 0,1} \right.
$$
Then for the even component it shall be
$$
\eqalign{
& i = 0\quad \Rightarrow \quad a \le 2j \le n\quad \Rightarrow \quad \left\lceil {{a \over 2}} \right\rceil \le j \le \left\lfloor {{n \over 2}} \right\rfloor
\quad \Rightarrow \cr
& \Rightarrow \quad \left\lfloor {{{a + 1} \over 2}} \right\rfloor \le j \le \left\lfloor {{n \over 2}} \right\rfloor \cr}
$$
and for the odd
$$
\eqalign{
& i = 1\quad \Rightarrow \quad a \le 2j - 1 \le n\quad \Rightarrow \quad \left\lceil {{{a + 1} \over 2}} \right\rceil \le j \le
\left\lfloor {{{n + 1} \over 2}} \right\rfloor \quad \Rightarrow \cr
& \Rightarrow \quad \left\lfloor {{{a + 2} \over 2}} \right\rfloor \le j \le \left\lfloor {{{n + 1} \over 2}} \right\rfloor \cr}
$$
Note that for the lower bound we shall employ the ceiling and the floor for the upper. Then we can convert the ceiling to floor.
The sum over $k$ of $f(k)$ can be split into the sum over the even and the odd component
$$
\eqalign{
& \sum\limits_{a\, \le \,k\, \le \;n} {f(k)} = \sum\limits_{a\, \le \,k\, \le \;n} {\left. {f(k)\,} \right|_{\,k = 2j} + \left. {f(k)\,} \right|_{\,k = 2j - 1} } = \cr
& = \sum\limits_{a\, \le \,2j\, \le \;n} {f(2j)} + \sum\limits_{a\, \le \,2j - 1\, \le \;n} {f(2j - 1)} = \cr
& = \sum\limits_{\left\lfloor {{{a + 1} \over 2}} \right\rfloor \le j \le \left\lfloor {{n \over 2}} \right\rfloor } {f(2j)}
+ \sum\limits_{\left\lfloor {{{a + 2} \over 2}} \right\rfloor \le j \le \left\lfloor {{{n + 1} \over 2}} \right\rfloor } {f(2j - 1)} \cr}
$$
and same for that of $(-1)^k f(k)$
$$
\eqalign{
& \sum\limits_{a\, \le \,k\, \le \;n} {\left( { - 1} \right)^{\,k} f(k)}
= \sum\limits_{\left\lfloor {{{a + 1} \over 2}} \right\rfloor \le j \le \left\lfloor {{n \over 2}} \right\rfloor } {\left( { - 1} \right)^{\,2j} f(2j)}
+ \sum\limits_{\left\lfloor {{{a + 2} \over 2}} \right\rfloor \le j \le \left\lfloor {{{n + 1} \over 2}} \right\rfloor } {\left( { - 1} \right)^{\,2j - 1} f(2j - 1)} = \cr
& = \sum\limits_{\left\lfloor {{{a + 1} \over 2}} \right\rfloor \le j \le \left\lfloor {{n \over 2}} \right\rfloor } {f(2j)}
- \sum\limits_{\left\lfloor {{{a + 2} \over 2}} \right\rfloor \le j \le \left\lfloor {{{n + 1} \over 2}} \right\rfloor } {f(2j - 1)} \cr}
$$
Now, just subtract the two above to confirm the thesis.
--- addendum ----
Concerning your request on how to transform ceiling <-> floor, consider that
$$
\eqalign{
& n = 2\left\lceil {{n \over 2}} \right\rceil + 2\left\{ {{n \over 2}} \right\} = 2q + i\quad \left| \matrix{
\;n,q \in Z \hfill \cr
\,i = 0,1 \hfill \cr} \right. \cr
& \left\lceil {{n \over 2}} \right\rceil = \left\lceil {{{2q + i} \over 2}} \right\rceil
= \left\lceil {q + {i \over 2}} \right\rceil = q + \left\lceil {{i \over 2}} \right\rceil = q + i \cr
& \left\lfloor {{{n + 1} \over 2}} \right\rfloor = \left\lfloor {{{2q + 1 + i} \over 2}} \right\rfloor
= \left\lfloor {q + {{1 + i} \over 2}} \right\rfloor = q + \left\lfloor {{{1 + i} \over 2}} \right\rfloor = q + i \cr}
$$
and, in general
$$
\left\lceil {{n \over m}} \right\rceil = \left\lfloor {{{n + m - 1} \over m}} \right\rfloor \quad \left| \matrix{
\;n,m \in Z \hfill \cr
\;1 \le m \hfill \cr} \right.
$$
re. for details to this article.
Best Answer
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.