telescoping series

To find \sum_{k=1}^n u_k, write each term as t_k-t_{k+1}. Then u_1+u_2+u_3+\dots+u_n=(t_1-t_2)+(t_2-t_3)+(t_3-t_4)+\dots+(t_n-t_{n+1})=t_1-t_{n+1}

This is analogous to integration: \int_a^b F'(t) dt=F(b)-F(a).
And practically exactly the same thing as the finite calculus version of integration, summation.
All series are telescoping series!
Find the sum of 1\times2+2\times3+3\times4+4\times5+\cdots+n(n+1).
To convert this to a telescoping series, we need to find a way of expressing each term as t_n-t_{n+1}.
Maybe the e.g. 3\times4 term can be extended in both directions, 2\times3\times4 and 3\times4\times5, and expressed as the difference of multiples of these, i.e. (n-1)n(n+1) and n(n+1)(n+2).
Noting that (n+2)-(n-1)=2+1=3, we can use the multiply by 1 cleverly tool to find the desired expression.

    \begin{align*} n(n+1)&=n(n+1)\times\frac{(n+2)-(n-1)}{3} \\ &=\frac{n(n+1)(n+2)}{3}-\frac{(n-1)n(n+1)}{3} \\ \text{So } \sum_{k=1}^n k(k+1)&=\frac{1.2.3-0.1.2+2.3.4-1.2.3+3.4.5-2.3.4 +\cdots}{3} \\ \cdots+&\frac{(n-1)n(n+1)-(n-2)(n-1)n}{3} \\ &+\frac{n(n+1)(n+2)-(n-1)n(n+1)}{3} \\ \intertext{Everything cancels out except the $n(n+1)(n+2)$ term, leaving} \sum_{k=1}^n k(k+1)&=\frac{n(n+1)(n+2)}{3} \end{align*}

In terms of falling powers, as is usual in finite calculus:

    \[\sum_{x=1}^n \fp{x}{2}=\frac{\fp{(n+1)}{3}}{3}\]

(This is the finite calculus version of the more familiar \displaystyle\int_0^n x^2 \text{ d}x=\frac{n^3}{3}.)

Applications etc

Common ad nauseam in the telescoping literature is the one arising from \fr{n(n+1)}=\fr{n}-\fr{n+1}, which I was thus going to avoid here, until I found an interesting version due to Marc Frantz.
The nth telephone pole appears at x=x_n. From the side ratios of similar triangles we get:

    \begin{align*} \frac{x_n}{n}&=\frac{1-x_n}{1} \\ x_n&=\frac{n}{n+1}  \end{align*}

The nth gap, between x_{n-1} and x_n, is: \displaystyle a_n=x_n-x_{n-1}&=\fr{n(n+1)}

The poles appear between x=0 and x=1, i.e. the sum of the series (of gaps) is 1.

\displaystyle \sum_{n=1}^\infty \fr{n(n+1)}=\sum_{n=1}^\infty (\fr{n}-\fr{n+1})=1

Partial sums of a geometric series

If x=1, then s^n=n. If x\neq 1, then

    \begin{align*} (1-x)s^n&=1-x+x-x^2+x^2-x^3+\dots+x^{n-1}-x^n \\ s^n&=\frac{1-x^n}{1-x} \\ &=\frac{1}{1-x}-\frac{x^n}{1-x} \end{align*}

If |x|<1 then x^n\to 0 as n\to\infty, and the series converges to \fr{1-x}.

Example: Find \ \displaystyle\sum_{k=1}^n  k!k.

    \begin{align*} k!k &=k!(k+1-1) \ \ \ \text{ (add 0 creatively)}\\ & =(k+1)!-k! \\ \text{So } \sum_{k=1}^n k!k &=\sum_{k=1}^n((k+1)!-k!)=(n+1)!-1. \end{align*}

Example: Using a telescoping series, find the closed form expression for \sum_{n=1}^N n^2.

We need an expression with n^2 and f(n+1)-f(n) terms, for some function f.
Since n+1-n=1, and (n+1)^2-n^2=2n+1, we expect (n+1)^3-n^3 to be an expression in n^2, so try that.

    \begin{align*} (n+1)^3-n^3 &=n^3+3n^2+3n+1-n^3 \\ &=3n^2+3n+1 \\ \text{So } \ \ 3n^2&=(n+1)^3-n^3-3n-1 \\ \intertext{Summing both sides from $n=1$ to $N$,} 3\sum_{n=1}^N n^2 &= \sum_{n=1}^N \big( (n+1)^3-n^3 \big) - 3\sum_{n=1}^N n-\sum_{n=1}^N 1 \\ &= (N+1)^3-N^2+N^2-(N-1)^2+\dots \\ &\quad \dots+3^3-2^3+2^3-1^3-\frac{3N(N+1)}{2}-N \\ &=(N+1)^3-1-\frac{3N(N+1)}{2}-N \\ &=\frac{(N+1)(2N^2+4N+2-3N)-2N-2}{2} \\ &= \frac{(N+1)(2N^2+N+2-2)}{2} \\ &= \frac{N(N+1)(2N+1)}{2} \\ \intertext{So} \sum_{n=1}^N n^2 &= \frac{N(N+1)(2N+1)}{6} \end{align*}

Pascal’s method (1654) of summing powers of positive integers.
First find S_1=1+2+3+\cdots, then use S_1 to find S_2=1^2+2^2+3^2+\cdots, S_2 to find S_3 and so on.

    \begin{align*} (k+1)^2-k^2&=2k+1 \\ \sum_{k=1}^n \big( (k+1)^2-k^2 \big)&=(n+1)^2-1 \text{ (by telescoping)} \\  &= \sum_{k=1}^n (2k+1) =2\sum_{k=1}^n k + n=2S_1+n\\ \text{So } (n+1)^2-1&=2S_1+n \\ n^2+n&=2S_1 \\ S_1&=\frac{n(n+1)}{2} \intertext{Similarly,} \sum_{k=1}^n \big( (k+1)^3-k^3 \big) &= \sum_{k=1}^n (3k^2+3k+1) \\ (n+1)^3-1 &=\binom{3}{2}S_2+\binom{3}{1}S_1+n \\ \sum_{k=1}^n \big( (k+1)^4-k^4 \big) &= \sum_{k=1}^n (4k^3+6k^2+4k+1) \\ (n+1)^4-1 &=\binom{4}{3}S_3+\binom{4}{2}S_2+\binom{4}{1}S_1+n \\ \sum_{k=1}^n \big( (k+1)^r-k^r \big) &= \sum_{k=1}^n \Bigg(\binom{r}{r-1}k^{r-1}+\binom{r}{r-2}k^{r-2}+\cdots \\ &\cdots+ \binom{r}{2}k^2+\binom{r}{1}k+1\Bigg) \\ (n+1)^r-1 &= \binom{r}{r-1}S_{r-1}+\binom{r}{r-2}S_{r-2}+\cdots \\ &\cdots+\binom{r}{2}S_2+\binom{r}{1}S_1+n  \end{align*}

useful identities

    \begin{align*} \fr{k(k+1)}&=\fr{k}-\fr{k+1} \\ x^4 + 4 &= x^4+4x^2+4-4x^2 \text{ (add 0 creatively)} \\ &= (x^2+2)^2-(2x)^2 \\ &=(x^2-2x+2)(x^2+2x+2) \\ (x+y)^2 &=x^2+2xy+y^2 \\ (x-y)^2 &=x^2-2xy+y^2 \\ (x + y)^3 &= x^3 + 3x^2 y + 3xy^2 + y^3 = x^3 + y^3 + 3xy(x + y) \\ (x - y)^3 &= x^3 - 3x^2 y + 3xy^2 - y^3 = x^3 - y^3 - 3xy(x - y) \\ x^2 - y^2 &= (x - y) (x + y) \\ x^n-y^n &= (x - y) (x^{n-1}+x^{n-2}y+x^{n-3}y^2+\dots+y^{n-1}) \text{ for all } n \\ x^n + y^n &= (x+ y)(x^{n-1}-x^{n-2}y+x^{n-3}y^2-\dots+y^{n-1}) \text{for all odd } n \\ \sum_{k=b+1}^\infty \fr{k^2-b^2} &= \fr{2b} \sum_{k=1}^{2b} \fr{k} \\ \text{e.g. }& \fr{3}+\fr{8}+\fr{15}+\fr{24}+\dots=\fr{2}(\fr{1}+\fr{2})=\frac{3}{4} \\ \end{align*}


Telescoping Sums, Series and Products at
Paul Zeitz – The Art and Craft of Problem Solving
Thomas Osler – Some Long Telescoping Series
J. Marshall Ash and Stefan Catoiu – Telescoping, rational-valued series, and zeta functions, Trans. Amer. Math. Soc. 357 (2005), p3339-58 PDF
Marc Frantz – The Telescoping Series in Perspective, Mathematics Magazine, Vol. 71, No. 4, Oct 1998