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!
e.g.
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 $n$ th 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 $n$ th 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

$s_n=1+x+x^2+\dots+x^{n-1}$ .
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*}$

more

Telescoping Sums, Series and Products at cut-the-knot.org
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