# 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?

-
Maybe Bill Dubuque should get first crack at answering this question? :) –  Mike Spivey Dec 9 '10 at 19:16
As to (3), it's the related use of the word telescoping in a mechanical sense (see this wikipedia stub). –  Isaac Dec 9 '10 at 19:20
Isaac was talking about contraptions like this. Searching Google Images for "collapsing telescope" should give you a good idea on how the name was applied to this peculiar technique of collapsing sums and products. –  Ｊ. Ｍ. Dec 10 '10 at 1:38
I realize that now and I suppose the term fits pretty nicely (which is why I deleted my previous comment). The problem I was having is that since I have a physics background, and I especially love astronomy, when I hear the word "telescope" I think of things like this and this ; ) –  Matt Calhoun Dec 10 '10 at 2:24
Well, "telescoping" here is pretty vintage, coined and used before those beasts in your pics were a twinkle in their respective inventors' eyes. –  Ｊ. Ｍ. Dec 10 '10 at 2:37

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.

-
A recent answer using these ideas: math.stackexchange.com/questions/8775/… –  Robin Chapman Dec 9 '10 at 19:23

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".

-