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:
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 .
Let’s warm up by solving a similar function (which will be instrumental later on), the sum . This is known as the geometric series. Put:
Let us combine the two:
This is a telescoping sum and terms mostly cancel each other out:
There, we’re done for this one. Reversing into is allowed because we multiply both the numerator and the denominator by (thus the whole expression by , so it doesn’t change its value).
Now, back to our main concern, the truncated staircase. Put:
So you’re guessing right, we’ll use the same overall trick as we did for the geometric series. Quite so!
After much pericombobulations, we, at last, get our solution:
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 . The denominator is zero, which is bad. But fortunately, is 1, so we have:
which is a sum you should already know:
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 suddenly becomes a , 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 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.