Telescoping Sums, Series and Products

The term Telescoping sum applies to en expression of the form

$\displaystyle \sum_{k=0}^{n}(a(k+1)-a(k)) $

which can be seen to equal $a(n+1)-a(0)$ in at least two ways. The first one illuminates the reason for the nomenclature. Write the addition implied by the summation shorthand explicitly:

$ (a(1)-a(0))\\ \space\space\space+(a(2)-a(1))\\ \space\space\space\space\space\space+(a(3)-a(2))\\ \ldots\\ \space\space\space\space\space\space\space\space\space+(a(n+1)-a(n)), $

and observe that all the intermediate terms in the sum cancel out, leaving the last and the first: $a(n+1)-a(0).$ The same result can be obtained by a rearrangement of terms:

$\displaystyle \begin{align} \sum_{k=0}^{n}(a(k+1)-a(k)) &= \sum_{k=0}^{n}a(k+1)-\sum_{k=0}^{n}a(k)\\ &= \sum_{k=1}^{n+1}a(k)-\sum_{k=0}^{n}a(k)\\ &= \bigg(\sum_{k=1}^{n}a(k)+a(n+1)\bigg)-\bigg(\sum_{k=1}^{n}a(k)+a(0)\bigg)\\ &= a(n+1)-a(0). \end{align}$

The concept of telescoping extends to infinite series:

$\displaystyle \begin{align} \sum_{k=0}^{\infty}(a(k+1)-a(k)) &= \lim_{n\rightarrow\infty}\sum_{k=0}^{n}(a(k+1)-a(k))\\ &= \lim_{n\rightarrow\infty}(a(n+1)-a(0))\\ &= \lim_{n\rightarrow\infty}a(n+1)-a(0). \end{align}$

such that the series converges, provided $\displaystyle\lim_{n\rightarrow\infty}a(n)$ exists.

The concept of telescoping extends to finite and infinite products. E.g.

$\displaystyle\prod_{k=1}^{n}\frac{f(k+1)}{f(k)}=\frac{f(n+1)}{f(1)}.$

Below I'll give several examples, the first absolutely classical, of application of the telescoping technique.

Since $\displaystyle\frac{1}{k(k+1)}=\frac{1}{k}-\frac{1}{k+1}$ we indeed have a telescoping series such that

$\displaystyle \begin{align} \sum_{k=0}^{\infty}\frac{1}{k(k+1)}&=\lim_{k\rightarrow\infty}\bigg(\frac{1}{1}-\frac{1}{k+1}\bigg)\\ &=1. \end{align}$

$p$ in the expression is assumed to be a positive integer.

Note that $\displaystyle\frac{1}{k(k+p)}=\frac{1}{p}\bigg(\frac{1}{k}-\frac{1}{k+p}\bigg),$ and continue

$\displaystyle \begin{align} \sum_{k=1}^{\infty}\frac{1}{k(k+p)}&=\lim_{n\rightarrow\infty}\sum_{k=1}^{n}\frac{1}{k(k+p)}\\ &=\lim_{n\rightarrow\infty}\frac{1}{p}\sum_{k=1}^{n}\bigg(\frac{1}{k}-\frac{1}{k+p}\bigg)\\ &=\frac{1}{p}\lim_{n\rightarrow\infty}\bigg(\sum_{k=1}^{n}\frac{1}{k}-\sum_{k=1}^{n}\frac{1}{k+p}\bigg)\\ &=\frac{1}{p}\lim_{n\rightarrow\infty}\bigg(\sum_{k=1}^{n}\frac{1}{k}-\sum_{k=p+1}^{n+p+1}\frac{1}{k}\bigg)\\ &=\frac{1}{p}\lim_{n\rightarrow\infty}\bigg(\sum_{k=1}^{p}\frac{1}{k}-\sum_{k=n+1}^{n+p+1}\frac{1}{k}\bigg)\\ &=\frac{1}{p}\bigg(\sum_{k=1}^{p}\frac{1}{k}-\lim_{n\rightarrow\infty}\sum_{k=1}^{p+1}\frac{1}{n+k}\bigg)\\ &=\frac{1}{p}\sum_{k=1}^{p}\frac{1}{k}. \end{align}$

For example, $\displaystyle\sum_{k=1}^{\infty}\frac{1}{k(k+2)}=\frac{3}{4}$ and $\displaystyle\sum_{k=1}^{\infty}\frac{1}{k(k+3)}=\frac{11}{18}.$

For a fixed integer $n\gt 0,$ let $\displaystyle f(a)=\prod_{k=1}^{n}(1+a^{2^k}).$ Then

$\begin{align} \displaystyle (1-a)f(a)&=(1-a)(1+a)(1+a^{2})(1+a^{4})\cdots (1+a^{2^n})\\ &=(1-a^{2})(1+a^{2})(1+a^{4})\cdots (1+a^{2^n})\\ &=(1-a^{4})(1+a^{4})\cdots (1+a^{2^n})\\ &=\ldots\\ &=(1-a^{2^n})(1+a^{2^n})\\ &=(1-a^{2^{n+1}}), \end{align}$

implying that $\displaystyle f(a)=\frac{1-a^{2^{n+1}}}{1-a}.$ Now assuming, $0\lt a\lt 1$ and passing to the limit,

$\displaystyle\prod_{k=1}^{\infty}(1+a^{2^k})=\frac{1}{1-a}.$

Note that the sum is finite; this is because the corresponding series is divergent.

$\displaystyle \begin{align} \sum_{k=0}^{n}\frac{1}{\sqrt{k+1}+\sqrt{k}}&=\sum_{k=0}^{n}\frac{\sqrt{k+1}-\sqrt{k}}{(k+1)-k}\\ &=\sum_{k=0}^{n}(\sqrt{k+1}-\sqrt{k})\\ &=\sqrt{n+1}-\sqrt{0}=\sqrt{n+1}. \end{align}$

Recollect that $cos(\alpha\pm\beta)=\cos\alpha\cos\beta\mp\sin\alpha\sin\beta,$ so that

$\cos(\alpha -\beta)-\cos(\alpha +\beta)=2\sin\alpha\sin\beta.$

From here, $\cos(2k-1)-\cos(2k+1)=2\sin 2k\cdot\sin 1.$ It follows that

$\displaystyle \begin{align} \sum_{k=1}^{n}\sin(2k)&=\frac{1}{2\sin 1}\sum_{k=1}^{n}(\cos(2k-1)-\cos(2k+1))\\ &=\frac{1}{2\sin 1}(\cos 1-\cos(2n+1)).\\ \end{align}$

A similar example - $\sin1^\circ+\sin2^\circ+\sin3^\circ+\cdots+\sin180^\circ=\tan89.5^\circ$ - can be found on a separate page.

By the same token as in the previous example,

$\cos\alpha\cdot\sin\beta=\frac{1}{2}(\sin(\alpha+\beta)-\sin(\alpha-\beta)).$

Now, $\displaystyle\cos(\pi\frac{2k+1}{2n+1})\sin\frac{\pi}{2n+1}=\frac{1}{2}(\sin\frac{2k+2}{2n+1}-\sin\pi\frac{2k}{2n+1}),$ and this shows that the sum in the caption is telescoping:

$\begin{align}\displaystyle \sum_{k=0}^{n-1}\cos(\pi\frac{2k+1}{2n+1})&=\frac{1}{2\sin\pi\frac{1}{2n+1}}\sin\pi\frac{2n}{2n+1}\\ &=\frac{1}{2\sin\pi\frac{1}{2n+1}}\sin\pi\frac{1}{2n+1}\\ &= \frac{1}{2}, \end{align}$

irrespective of $n!$ (Here I used $\sin(\pi-\alpha)=\sin\alpha.$) This generalizes Problem 5 from the 1963 IMO.

This sum is a part of problem #13 from a recent book Jim Totten's Problems of the Week.

To simplify the expressions, define $a=\sqrt[3]{k+1}$ and $b=\sqrt[3]{k-1}.$ Then

$\displaystyle \begin{align} f(k)&=\frac{1}{a^2+ab+b^2}\\ &=\frac{a-b}{a^3-b^3}=\frac{a-b}{2}=\frac{1}{2}(\sqrt[3]{k+1}-\sqrt[3]{k-1}), \end{align}$

which shows that the sum at hand is telescoping:

$F(2n+1)=\frac{1}{2}(\sqrt[3]{(2n+1)+1}-\sqrt[3]{0}).$

It follows that $F(999999)=\frac{1}{2}(\sqrt[3]{1000000})=\frac{100}{2}=50.$

References

1. J. G. McLoughlin et al, Jim Totten's Problems of the Week, World Scientific, 2013, #13

This is straightforward:

$\displaystyle\frac{k-\sqrt{k^2-1}}{\sqrt{k(k-1)}}=\frac{\sqrt{k}}{\sqrt{k+1}}-\frac{\sqrt{k-1}}{\sqrt{k}} $

so that $\displaystyle\sum_{k=0}^{\infty}\frac{k-\sqrt{k^2-1}}{\sqrt{k(k+1)}}=\lim_{n\rightarrow\infty}\sqrt{\frac{n}{n+1}}=1.$

This is a modification of problem 903 from The College Mathematics Journal, v. 41, n 3, May 2010, and was also considered elsewhere.

1. $\displaystyle\sum_{k=0}^{n}k\cdot k!=(n+1)!-1$

   Simply observe that $k\cdot k!=(k+1)!-k!$

2. $\displaystyle\sum_{k=0}^{n}\frac{k}{(k+1)!}=1-\frac{1}{(n+1)!}$

   Same as above: $\displaystyle \frac{k}{(k+1)!}=\frac{1}{k!}-\frac{1}{(k+1)!}$

3. $\displaystyle\sum_{k=0}^{\infty}\frac{1}{C_{k}^{n+k}}=\frac{n}{n-1}$

   Proof

4. $\displaystyle\sum_{k=0}^{n}k^{2}=\frac{n(n+1)(2n+1)}{6}$

   Try doing that before looking into the next example.

5. $\displaystyle\sum_{k=0}^{n}n^{3}=\bigg[\frac{n(n+1)}{2}\bigg]^{2}$

   Proof

6. $\displaystyle 2^{2013}\cos ^{4026}\bigg(\frac{1}{2}\bigg)\cos ^{4025}\bigg(\frac{1}{3}\bigg)\cos ^{4024}\bigg(\frac{1}{4}\bigg)\cdots\cos \bigg(\frac{1}{4027}\bigg)\gt\sqrt{2014}$

   Proof

7. $\displaystyle\sum_{k=1}^{n}k\cdot n^{n-k}\cdot A^{k-1}_{n-1}=n^n,$ where $A_{x}^{y}$ is the number of permutations of $x$ elements out of $y:$ $\displaystyle A_{x}^{y}=\frac{y!}{(y-x)!}$

   Proof

8. $\displaystyle\cos \frac{\pi}{7}-\cos \frac{2\pi}{7}+\cos \frac{3\pi}{7} = \frac{1}{2}$

   Proof

9. The sequence $a_n$ is defined by $a_{1}=1$ and $a_{k+1}=(k+1)(a_{k}+1)$ for all $k\gt 1$ Find $\displaystyle\prod_{k+1}^{\infty}\left(1+\frac{1}{a_k}\right)$

   Solution

10. $\displaystyle\sum_{k=1}^{n}\frac{1}{\sqrt{k}}\gt 2(\sqrt{n+1}-1)$

    Solution

11. $\displaystyle S(n)=\sum_{k=1}^n\frac{\sin 1}{\cos (k-1)\cos k}$

    Solution

12. Solve $\displaystyle \frac{1^2\cdot 2!+2^2\cdot 3!+...+n^2(n+1)!-2}{(n+1)!}=108.$

    See Solution 2

1. T. Andreescu, R. Gelca, Mathematical Olympiad Challenges, Birkhäuser, 2004, 5^th printing, ch 1.9
2. R. Gelca, T. Andreescu, Putnam and Beyond, Springer, 2007, ch 3.1.6
3. P. Zeitz, The Art and Craft of Problem Solving, John Wiley & Sons, 1999, ch 5.3