Telescoping series

Find $S_r = 1^r + 2^r + 3^r + ... + n^r$ where r is any fixed positive integer in terms of $S_1, S_2, ... S_{r-1}$.

Age

16 to 18

Challenge level

Exploring and noticing Working systematically Conjecturing and generalising Visualising and representing Reasoning, convincing and proving

Being curious Being resourceful Being resilient Being collaborative

Problem

In 1654 Blaise Pascal published a general method for summing powers of positive integers, i.e. summing all the series.

S_{1} = 1 + 2 + 3 + . . . + n

S_{2} = 1^{2} + 2^{2} + 3^{2} + . . . + n^{2}

S_{3} = 1^{3} + 2^{3} + 3^{3} + . . . + n^{3}

\dots

S_{r} = 1^{r} + 2^{r} + 3^{r} + . . . + n^{r}

Pascal's method uses the coefficients which appear in Pascal's triangle and in the Binomial Theorem, first finding $S_1$, and then using $S_1$ to find $S_2$, and then using both to find $S_3$, and so on. The method applies, where $r$ is any fixed positive integer, to:

S_{r} = \sum_{k = 1}^{n} k^{r} .

Case 1: $r = 1$

Simplify $(k+1)^2 - k^2$ and hence show that:

\sum_{k = 1}^{n} [(k + 1)^{2} - k^{2}] = (\binom{2}{1}) S_{1} + n .

Write the sum out in full for $n = 6$. Use this method to prove that $S_1=n(n+1)/2$.

Case 2: $r = 2$

Simplify $(k+1)^3 - k^3$ and hence show that

\sum_{k = 1}^{n} [(k + 1)^{3} - k^{3}] = (n + 1)^{3} - 1 = (\binom{3}{1}) S_{2} + (\binom{3}{2}) S_{1} + n .

Hence prove that $S_2 = n(n+1)(2n + 1)/6$.

Case 3: $r = 3$

Use this technique to find $1^3 + 2^3 + 3^3 + ... + 10^3$.

General case

Show that

(n + 1)^{r} - (n + 1) = (\binom{r}{1}) S_{1} + (\binom{r}{2}) S_{2} + (\binom{r}{3}) S_{3} + \dots (\binom{r}{r - 1}) S_{r - 1} .

Student Solutions

Congratulations to Herbert Pang of Sha Tin College, Hong Kong and also to Ka Wing Kerwin Hui for their excellent solutions. Both of these solutions were written in Word 97 using Equation Editor 3.0 and are beautifully presented.

Case 1: $r=1$

We simplify $(k + 1)^2 - k^2$. Writing the binomial coefficients in the form

(\binom{n}{r}) = \frac{n!}{r! (n - r)!},

then for each $k$,

(k + 1)^{2} - k^{2} = k^{2} + (\binom{2}{1}) k + 1 - k^{2} = (\binom{2}{1}) k + 1;

hence

\sum_{k = 1}^{n} [(k + 1)^{2} - k^{2}] = \sum_{k = 1}^{n} [(\binom{2}{1}) k + 1] = \sum_{k = 1}^{n} (\binom{2}{1}) k + \sum_{k = 1}^{n} 1.

Writing $S_r$ for $\sum^n_{k=1} k^r$, this gives

\sum_{k = 1}^{n} [(k + 1)^{2} - k^{2}] = (\binom{2}{1}) S_{1} + n .

Writing this sum in full for $n=6$ we note that terms cancel out in pairs (hence the name 'telescoping series') giving:

[2^{2} - 1^{2}] + [3^{2} - 2^{2}] + [4^{2} - 3^{2}] + [5^{2} - 4^{2}] + 6^{2} - 5^{2}] + [7^{2} - 6^{2}] = - 1 + 49 = 48

If we write this out in full with a general $n$ we get

[2^{2} - 1^{2}] + [3^{2} - 2^{2}] + [4^{2} - 3^{2}] + \dots + [(n + 1)^{2} - n^{2}] = - 1 + (n + 1)^{2} = n^{2} + 2 n .

Hence

n^{2} + 2 n = 2 S_{1} + n,

and this gives

S_{1} = n (n + 1) / 2.

Case 2: $r=2$

We simplify $(k + 1)^3 - k^3$. For any $k$,

(k + 1)^{3} - k^{3} = k^{3} + (\binom{3}{1}) k^{2} + (\binom{3}{2}) k + 1 - k^{3} = (\binom{3}{1}) k^{2} + (\binom{3}{2}) k + 1,

and adding this for $k=1,\ldots , n$, we get

\sum_{k = 1}^{n} [(k + 1)^{3} - k^{3}] = \sum_{k = 1}^{n} [(\binom{3}{1}) k^{2} + (\binom{3}{2}) k + 1] = (\binom{3}{1}) S_{2} + (\binom{3}{2}) S_{1} + n .

The left hand side is a telescoping series, and is

[2^{3} - 1^{3}] + [3^{3} - 2^{3}] + [4^{3} - 3^{3}] + \dots + [(n + 1)^{3} - n^{3}] = - 1 + (n + 1)^{3} = n^{3} + 3 n^{2} + 3 n,

so that

n^{3} + 3 n^{2} + 3 n = (\binom{3}{1}) S_{2} + (\binom{3}{2}) S_{1} + n .

As we have already found $S_1$ to be $n(n + 1)/2$, we can now find the formula for $S_2$:

n^{3} + 3 n^{2} + 3 n = 3 S_{2} + 3 n (n + 1) / 2 + n .

Simplifying this gives

S_{2} = \frac{n (n + 1) (2 n + 1)}{6} .

Case 3: $r=3$

We simplify $(k + 1)^4 - k^4$. For any $k$,

(k + 1)^{4} - k^{4} = k^{4} + (\binom{4}{1}) k^{3} + (\binom{4}{2}) k^{2} + (\binom{4}{3}) k + 1 - k^{4} = (\binom{4}{1}) k^{3} + (\binom{4}{2}) k^{2} + (\binom{4}{3}) k + 1

and adding this for $k=1,\ldots , n$, we get

\sum_{k = 1}^{n} [(k + 1)^{4} - k^{4}] = \sum_{k = 1}^{n} [(\binom{4}{1}) k^{3} + (\binom{4}{2}) k^{2} + (\binom{4}{3}) k + 1] = (\binom{4}{1}) S_{3} + (\binom{4}{2}) S_{2} + (\binom{4}{3}) S_{1} + n

The left hand side is a telescoping series, and is

[2^{4} - 1^{4}] + [3^{4} - 2^{4}] + [4^{4} - 3^{4}] + \dots + [(n + 1)^{4} - n^{4}] = - 1 + (n + 1)^{4} = n^{4} + 4 n^{3} + 6 n^{2} + 4 n

so that

n^{4} + 4 n^{3} + 6 n^{2} + 4 n = (\binom{4}{1}) S_{3} + (\binom{4}{2}) S_{2} + (\binom{4}{3}) S_{1} + n

Using the formulae for $S_1$ and $S_2$, we obtain an equation for $S_3$, and simplifying this we get

S_{3} = \frac{n^{2} (n + 1)^{2}}{4} .

For $n=10$ we get

\sum_{k = 1}^{10} k^{3} = \frac{10^{2} \times 11^{2}}{4} = 3025.

It is interesting to note that for all $n$,

S_{3} = {(\frac{n (n + 1)}{2})}^{2} = (S_{2})^{2} .

General case

We simplify $(k + 1)^r - k^r$. For any $k$,

(k + 1)^{r} - k^{r} = (\binom{r}{1}) k^{r - 1} + (\binom{r}{2}) k^{r - 2} + \dots + (\binom{r}{r - 1}) k + 1,

and adding this for $k=1,\ldots , n$, we get

\sum_{k = 1}^{n} [(k + 1)^{r} - k^{r}] = (\binom{r}{1}) S_{r - 1} + (\binom{r}{2}) S_{r - 2} + \dots + (\binom{r}{r - 1}) S_{1} + n

The left hand side is a telescoping series, and is

[2^{r} - 1^{r}] + [3^{r} - 2^{r}] + [4^{r} - 3^{r}] + \dots + [(n + 1)^{r} - n^{r}] = - 1 + (n + 1)^{r}

hence

(n + 1)^{r} - 1 = (\binom{r}{1}) S_{r - 1} + (\binom{r}{2}) S_{r - 2} + \dots + (\binom{r}{r - 1}) S_{1} + n

Transferring $n$ from the right to the left, and using

(\binom{r}{k}) = (\binom{r}{r - k})

we get

(n + 1)^{r} - (n + 1) = (\binom{r}{1}) S_{1} + (\binom{r}{2}) S_{2} + \dots + (\binom{r}{r - 1}) S_{r - 1}

Or search by topic

Number and algebra

Geometry and measure

Probability and statistics

Working mathematically

Advanced mathematics

For younger learners

Telescoping series

Problem

Getting Started

Student Solutions

Teachers' Resources