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.

This entry was posted on Tuesday, October 27th, 2009 at 5:29 am and is filed under hacks, Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to Of staircases and textbooks

The Complex Beauty of Simplicity « Harder, Better, Faster, Stronger says:

May 4, 2010 at 5:10 am

[...] 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, [...]

Reply
Average node depth in a Full Tree | Harder, Better, Faster, Stronger says:

May 14, 2013 at 13:50 pm

[…] 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 . […]

Reply

Harder, Better, Faster, Stronger