Telescoping Sums, Series and Products

Introduction

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.

$\displaystyle\sum_{k=1}^{\infty}\frac{1}{k(k+1)}$

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}$

$\displaystyle\sum_{k=1}^{\infty}\frac{1}{k(k+p)}$

$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}.$

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

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}.$

$\displaystyle\sum_{k=0}^{n}\frac{1}{\sqrt{k+1}+\sqrt{k}}$

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}$

$\displaystyle\sum_{k=1}^{n}\sin(2k)$

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.

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

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.

$\displaystyle\sum_{k\space\mbox{odd}}^{n}\frac{1}{\sqrt[3]{k^2+2k+1}+\sqrt[3]{k^2-1}+\sqrt[3]{k^2-2k+1}}$

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

Let $f(k)=\displaystyle\frac{1}{\sqrt[3]{k^2+2k+1}+\sqrt[3]{k^2-1}+\sqrt[3]{k^2-2k+1}}$ and $F(2n+1)=f(1)+f(3)+f(5)+\ldots+f(2n+1).$

Find $F(999999).$

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

$\displaystyle\sum_{k=0}^{\infty}\frac{k-\sqrt{k^2-1}}{\sqrt{k(k-1)}}$

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.

Additional examples

  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}n^{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

References

  1. T. Andreescu, R. Gelca, Mathematical Olympiad Challenges, Birkhäuser, 2004, 5th 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

|Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2017 Alexander Bogomolny

 61177006

Search by google: