3.2 "Telescoping" series

Sometimes, we have sums where everything cancels out nicely. A specific form of this is called a \saytelescoping series, and the term refers to anything in the form

∑k=1n[f⁢(k+a)−f⁢(k)]\sum_{k=1}^{n}\left[f(k+a)-f(k)\right] (3.5)

Here, aa is a constant natural number (e.g. 1,2,3,…1,2,3,...) and kk is the index of summation.

The key idea is that eventually the −f⁢(k)-f(k) will "catch up" to the +f⁢(k+a)+f(k+a). If aa were equal to 11, for example, we would have that

∑k=1n[f⁢(k+1)−f⁢(k)]=f⁢(2)−f⁢(1)+f⁢(3)−f⁢(2)+f⁢(4)−f⁢(3)+…\sum_{k=1}^{n}\left[f(k+1)-f(k)\right]=f(2)-f(1)+f(3)-f(2)+f(4)-f(3)+... (3.6)

A lot of terms are going to cancel here! When we add f⁢(2)f(2) and −f⁢(2)-f(2) we get 0. The same thing happens for f⁢(3)f(3) and −f⁢(3)-f(3), and so on. Every −f⁢(k)-f(k) term in our series cancels out the f⁢(k)f(k) term from the previous term. This means that all the terms, except the first and the last terms are going to cancel each other out, leaving us with just

−f⁢(1)+f⁢(n)=f⁢(n)−f⁢(1)-f(1)+f(n)=f(n)-f(1) (3.7)

One way to visualise this it to rewrite the sum.

∑k=1n[f⁢(k+a)−f⁢(k)]\displaystyle\sum_{k=1}^{n}\left[f(k+a)-f(k)\right] =∑k=1n[f⁢(k+a)]−∑k=1n[f⁢(k)]\displaystyle=\sum_{k=1}^{n}\left[f(k+a)\right]-\sum_{k=1}^{n}\left[f(k)\right] (3.8)
=∑k=an+a[f⁢(k)]−∑k=1n[f⁢(k)]\displaystyle=\sum_{k=a}^{n+a}\left[f(k)\right]-\sum_{k=1}^{n}\left[f(k)\right] (3.9)
Example 3.2.1

Find a closed-form (read: nice) formula for the sum

∑1≦r≦n[(r2+r−1)⁢(r−1)!]\sum_{1\leqq r\leqq n}\left[(r^{2}+r-1)(r-1)!\right] (3.10)

The first step (assuming that we wish to solve this using a telescoping series) is to split the expression summand into two, which will telescope. The source I originally found this question from did first give the necessary identity which very much helps, but we can also work this out ourselves.

Let us first be very clear about what our goal is; we guess that the sum will telescope, and assuming that it does we must find some way of exploiting this. Specifically, we want to split the summand into two parts (which telescope).

It would be lovely if we could break r2+r−1r^{2}+r-1 into two parts which telescope. todo: why isn’t this possible

The other thing we can do is this

r2⁢(r−1)!−r⁢(r−1)!−(r−1)!\displaystyle r^{2}(r-1)!-r(r-1)!-(r-1)! (3.11)
=(r−1)!⁢(r2−r)−(r−1)!\displaystyle=(r-1)!(r^{2}-r)-(r-1)! (3.12)
=(r−1)!⁢(r)⁢(r+1)−(r−1)!\displaystyle=(r-1)!(r)(r+1)-(r-1)! (3.13)
=(r+1)!−(r−1)!\displaystyle=(r+1)!-(r-1)! (3.14)

Therefore,

∑1≦r≦n[(r2+r−1)⁢(r−1)!]\displaystyle\sum_{1\leqq r\leqq n}\left[(r^{2}+r-1)(r-1)!\right] =∑1≦r≦n(r+1)!−∑1≦r≦n(r−1)!\displaystyle=\sum_{1\leqq r\leqq n}(r+1)!-\sum_{1\leqq r\leqq n}(r-1)! (3.15)

Now we would like to exploit the telescoping property. Writing out the sum, we get something like this

(1+1)!−(0)!\displaystyle(1+1)!-(0)! (3.17)
+(2+1)!−(1)!\displaystyle+(2+1)!-(1)! (3.18)
+(3+1)!−(2)!\displaystyle+(3+1)!-(2)! (3.19)
+…\displaystyle+... (3.20)
+(n−1)!−(n−3)!\displaystyle+(n-1)!-(n-3)! (3.21)
+(n)!−(n−2)!\displaystyle+(n)!-(n-2)! (3.22)
+(n+1)!−(n−1)!\displaystyle+(n+1)!-(n-1)! (3.23)

After crossing out all the terms which are the same, we are left with

−(0)!−(1)!+(n)!+(n+1)!\displaystyle-(0)!-(1)!+(n)!+(n+1)! =n!⁢(1+(n+1))−2\displaystyle=n!(1+(n+1))-2 (3.24)
=(n+2)⁢n!−2\displaystyle=(n+2)n!-2 (3.25)