Of staircases and textbooks

This week, I’m talking you about a little identity that crops up often in the study of algorithms and which isn’t found in formula compendia—anyway, none that I have. I’m talking about this function:

\displaystyle C_{n,a}=\sum_{i=1}^n i a^i

This is a variation on the Gabriel’s Staircase function that does not have an infinite number of terms. Let us solve it without supposing that 0<a<1.

Let’s warm up by solving a similar function (which will be instrumental later on), the sum \sum_{i=1}^n a^i. This is known as the geometric series. Put:

t_n = \sum_{i=1}^n a^i

and

a t_n = a\sum_{i=1}^n a^i

Let us combine the two:

t_n - a t_n = (1-a)t_n = \sum_{i=1}^n a^i - a\sum_{i=1}^n a^i

t_n-at_n= (a+a^2+a^3+\cdots+a^n)-(a^2+a^3+a^4+\cdots+a^{n+1})

This is a telescoping sum and terms mostly cancel each other out:

t_n-at_n=(1-a)t_n = a-a^{n+1}

and finally:

\displaystyle t_n = \frac{a-a^{n+1}}{1-a}=\frac{a(1-a^n)}{1-a}=\frac{a(a^n-1)}{a-1}

There, we’re done for this one. Reversing (1-a) into (a-1) is allowed because we multiply both the numerator and the denominator by -1 (thus the whole expression by 1, so it doesn’t change its value).

Now, back to our main concern, the truncated staircase. Put:

\displaystyle s=\sum_{i=1}^n i a^i

and

\displaystyle as=a\sum_{i=1}^n ia^i=\sum_{i=1}^nia^{i+1}

So you’re guessing right, we’ll use the same overall trick as we did for the geometric series. Quite so!

\displaystyle s-as = \sum_{i=1}^n ia^i-\sum_{i=1}^nia^{i+1}

(1-a)s=(a+2a^2+3a^3+\cdots{}+na^n)-(a^2+2a^3+3a^4+\cdots{}+na^{n+1})

(1-a)s=a+a^2+a^3+\cdots{}+a^n-na^{n+1}

\displaystyle (1-a)s=\sum_{i=1}^n a^i - na^{n+1}

\displaystyle (1-a)s=\frac{a(1-a^n)}{1-a}- na^{n+1}

then

\displaystyle (1-a)s=\frac{(1-a^n)-(1-a)na^{n+1}}{1-a}

\displaystyle (1-a)s=\frac{a^{n+1}(na-n-1)+a}{1-a}

\displaystyle (1-a)s=\frac{a^{n+1}(n(a-1)-1)+a}{1-a}

After much pericombobulations, we, at last, get our solution:

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

*
* *

Despite all the work, only basic algebra is needed to obtain the desired expression, and, well, a lot of patience. We also note that a difficulty arises when a=1. The denominator is zero, which is bad. But fortunately, 1^x is 1, so we have:

s=\sum_{i=1}^{n} ia^i = \sum_{i=1}^{n} i(1^i) =\sum_{i=1}^{n} i

which is a sum you should already know:

s=\sum_{i=1}^{n} i = \frac{1}{2}n(n+1)

*
* *

A few friends of mine decided to return to school—well, the university, that is. And all of them have to take (or retake) math classes to enroll in their programs. They’re not all at the same level, but they’re quite decided and working hard to get there. However, I do hear complaints now and then and it’s mostly about how bad introductory-level textbooks are. In one book my friend Vincent showed me, a b suddenly becomes a 6, altering the derivation of the solution in ways that are more tragic than funny. I guess college-level textbooks do not all get that much of a scrutiny before release.

Another complaint I hear is how things are derived. While it may be perfectly acceptable in an advanced textbook to simply state that \sum_{i=1}^n i 2^i = 2^{n+1}(n-1)+2 and move on as you expect your readers to be able to take 5 or 10 minutes to obtain the result by themselves, that’s not something you can do too often in an introductory- or college-level textbook because, guess what, you’re teaching math to people that may not know enough math to know beforehand what’re you’re trying to teach them. Wait, what?

Clear, step by step, derivations of equations are sometimes necessary, and not always for college-level textbooks. Some authors are notoriously vague in derivation. Sentences like “it naturally follows” are proverbially antinomic.

3 Responses to Of staircases and textbooks

  1. […] Complex Beauty of Simplicity As I have said before, some of my friends took the very wise decision to go back to school (that is, university) and, […]

  2. […] should look familiar to you. But we have , so we need to transform it a bit so that we fall back again on the form . […]

  3. […] studying algorithms, there is a number of series and expression that keep showing up. A while ago, I discussed the special form . But that’s not the only one. Another form that keeps showing […]

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: