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.

stairs

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: