Mathematical Telescoping

Bill Dubuque has answered several questions by indicating that some form of "telescoping" is taking place. See this post and the links provided by Bill for more information.

I have never heard of "telescoping" until I read a few answers on here by Bill which refer to this notion. It seems fairly straightforward, basically you expand some expression using basic arithmetic, there is a minor miracle and lots of terms cancel out in a systematic way, and we are then able to solve the problem.

I suppose "telescoping" in this sense was something I always took for granted, and considered a low level "trick" to keep in my back pocket. However, considering the importance Bill seems to attach to this notion of telescoping, and considering that I have a great deal of respect for Bill based on the post's by him I have read, I was wondering if I'm not missing something about telescoping. There is no wiki article on the subject, and a Google search directs me to Bill's answers on SE!

Therefore I would like to ask:

1) What unintuitive results can I achieve with telescoping?

2) Is there a good reference which only discusses telescoping and applications, or is this concept too narrow for anyone to write a paper/book like this?

3) More trivially, am I missing something about what telescoping actually means? If not, then why is this called telescoping, because I don't see what this has to do with a telescope?

Solution 1:

1, 2) Telescoping is one of the ideas behind modern algorithms to automatically prove hypergeometric identities. These algorithms allow you, for example, to automatically prove binomial coefficient identities. The standard reference here is Petkovsek, Wilf, and Zeilberger's A=B.

3) The name comes from the process of collapsing a telescope, which is analogous to the collapsing of a telescoping sum.

Philosophically telescoping is the same as "discrete integration": telescoping a sum $\sum f(n)$ is the same as finding $g(n)$ such that $f(n) = g(n+1) - g(n)$. In that sense it is part of the theory of finite differences, although people probably don't call it "telescoping" in this context. The context in which I hear the term "telescoping" being used is high school math competitions. It's one of those basic ideas that everyone has in the back of their head, I suppose. It's elementary and effective when it applies, but usually there are more sophisticated methods available.

Edit: Some specific examples. The ur-example of a telescoping sum is probably

$$\sum_{k=1}^n \frac{1}{k(k+1)} = \sum_{k=1}^{n} \left( \frac{1}{k} - \frac{1}{k+1} \right) = 1 - \frac{1}{n+1}$$

and many people have seen this application, but probably far fewer have seen its generalization:

$$\sum_{k=1}^n \frac{1}{k(k+1)...(k+r)} = \frac{1}{r} \sum_{k=1}^n \left( \frac{1}{k(k+1)...(k+r-1)} - \frac{1}{(k+1)...(k+r)} \right) = \frac{1}{r} \left( \frac{1}{r!} - \frac{n!}{(n+r)!} \right).$$

The other classic example I remember from my competition days is

$$\sum_{k=1}^n \frac{k}{k^4 - k^2 + 1} = \frac{1}{2} \sum_{k=1}^n \left( \frac{1}{k^2 - k + 1} - \frac{1}{(k+1)^2 - (k+1) + 1} \right) = \frac{1}{2} \left( 1 - \frac{1}{n^2 + n + 1} \right)$$

although I have to admit I always found it a little contrived. Finally, telescoping was put to good use to solve this math.SE question I posed.

Solution 2:

The book A=B by Petkovsek, Wilf and Zeilberger is an extended exposition of the Wilf-Zeilberger method for summing series often called "creative telescoping".