## A Special Case…

Expressions with floors and ceilings ($\lfloor x \rfloor$ and $\lceil y \rceil$) are usually troublesome to work with. There are cases where you can essentially remove them by a change of variables.

Turns out, one form that regularly comes up in my calculations is $\lfloor \lg x \rfloor$, and it bugged me a while before I figured out the right way of getting rid of them (sometimes).

Let us start by an abstract case:

$\displaystyle h(m)=\sum_{i=1}^m \lfloor \lg i \rfloor f(i)$

where $m\sim 2^k$ (for now), and where $f(i)$ is some function that depends only on $i$. $\lfloor \lg i \rfloor$ grows by one each time $i$ doubles in magnitude. We can therefore write the preceding as

$\displaystyle h(m)=\sum_{j=0}^k j \sum_{i=2^j}^{2^{j+1}-1} f(i)$

where you can verify that $i$ still progresses from $1$ to $m$ as before, but we now have a different grouping what allows us to replace $\lfloor \lg i \rfloor$ by $j$, and factor it out. We can now simplify the sums depending on $i$ as a function of $j$ as

$\displaystyle h(m)=\sum_{j=0}^k j g(j)$

where $g(j)$ is an expression depending only on $j$. Finally, you can obtain a simplified expression for $h(m)$, the initial goal.

*
* *

So, where does the bounds come from? As I said earlier, $\lfloor \lg i \rfloor$ has natural boundaries of the form $2^j$, with $j=0,1,2,\ldots$. Indeed:

 $j$ $2^j$ $\sum_{l=0}^j 2^l$ 0 1 1 1 2 3 2 4 7 3 8 15 4 16 31 … … …

The generator of the series at the far right of the table isn’t very hard to guess: $2^{j+1}-1$.

It is a special case of a geometric series,

$\displaystyle \sum_{k=0}^{n-1}a r^k=a\frac{1-r^n}{1-r}$

With $a=1$, $r=2$, it does simplify to the expected:

$\displaystyle a\frac{1-r^n}{1-r}=(1)\frac{1-2^{n+1}}{1-2}=\frac{-2^{n+1}+1}{-1}=2^{n+1}-1$

*
* *

So by knowing how to sum powers of two (or any other constant, for that matter), we could remove $\lfloor \lg i \rfloor$ and get a simpler expression. While the change of variable and adapting the sums’ boundaries helps a great deal, it is the fact that the base of the logarithm is an integer that helps quite a lot. Indeed, can you see what’s the problem is the base of the logarithm is now $e$?

You guessed it right. Now, instead than having boundaries at integers of the form $2^j$, we must find where the function changes between some $e^j$ and $e^{j+1}$, which can be quite messier.