You may also like

problem icon

Degree Ceremony

What does Pythagoras' Theorem tell you about these angles: 90°, (45+x)° and (45-x)° in a triangle?

problem icon

OK! Now Prove It

Make a conjecture about the sum of the squares of the odd positive integers. Can you prove it?

problem icon

Overarch 2

Bricks are 20cm long and 10cm high. How high could an arch be built without mortar on a flat horizontal surface, to overhang by 1 metre? How big an overhang is it possible to make like this?

Telescoping Series

Stage: 5 Challenge Level: Challenge Level:2 Challenge Level:2

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 $$ {n \choose r} = \frac{n!}{r!(n-r)!}, $$ then for each $k$, $$ (k + 1)^2 - k^2 = k^2 + {2\choose 1}k + 1 - k^2 = {2\choose 1}k + 1;$$ hence $$\sum_{k=1}^n[(k + 1)^2-k^2] =\sum_{k=1}^n\left[{2\choose 1}k + 1\right] =\sum_{k=1}^n{2\choose 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] ={2\choose 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] + \cdots + [(n + 1)^2-n^2] = -1 + (n + 1)^2 = n^2 + 2n.$$ Hence $$ n^2 + 2n = 2S_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 + {3\choose 1}k^2 + {3\choose 2}k + 1 - k^3 = {3\choose 1}k^2 + {3\choose 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\left[{3\choose 1}k^2 + {3\choose 2}k + 1\right] ={3\choose 1}S_2 + {3\choose 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] + \cdots + [(n + 1)^3-n^3] = -1 + (n + 1)^3 = n^3 + 3n^2 + 3n,$$ so that $$ n^3 + 3n^2 + 3n = {3\choose 1}S_2 + {3\choose 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 + 3n^2 + 3n = 3S_2 + 3n(n + 1)/2 + n.$$ Simplifying this gives $$ S_2 = {n(n + 1)(2n + 1)\over 6}.$$

Case 3: $r=3$

We simplify $(k + 1)^4 - k^4$. For any $k$, $$(k + 1)^4 - k^4 = k^4 + {4\choose 1}k^3 + {4\choose 2}k^2 + {4\choose 3}k + 1 - k^4 = {4\choose 1}k^3 + {4\choose 2}k^2 + {4\choose 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\left[{4\choose 1}k^3 + {4\choose 2}k^2 + {4\choose 3}k + 1\right] = {4\choose 1}S_3 + {4\choose 2}S_2 + {4\choose 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] + \cdots + [(n + 1)^4-n^4] = -1 + (n + 1)^4 = n^4 + 4n^3 + 6n^2 + 4n$$ so that $$ n^4 + 4n^3 + 6n^2 + 4n = {4\choose 1}S_3 + {4\choose 2}S_2 + {4\choose 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 = {n^2(n + 1)^2\over 4}.$$ For $n=10$ we get $$ \sum_{k=1}^{10}k^3 = {10^2\times 11^2\over 4} = 3025.$$ It is interesting to note that for all $n$, $$S_3 = \left({n(n + 1)\over 2}\right)^2 = \big(S_2\big)^2.$$

General case

We simplify $(k + 1)^r - k^r$. For any $k$, $$(k + 1)^r - k^r = {r\choose 1}k^{r-1} + {r\choose 2}k^{r-2} + \cdots + {r\choose r-1}k + 1,$$ and adding this for $k=1,\ldots , n$, we get $$ \sum_{k=1}^n[(k + 1)^r-k^r] = {r\choose 1}S_{r-1} + {r\choose 2}S_{r-2} + \cdots + {r\choose 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] + \cdots + [(n + 1)^r-n^r] = -1 + (n + 1)^r$$ hence $$ (n + 1)^r-1 = {r\choose 1}S_{r-1} + {r\choose 2}S_{r-2} + \cdots + {r\choose r-1}S_1 + n$$ Transferring $n$ from the right to the left, and using $$ {r\choose k} = {r\choose r-k}$$ we get $$(n + 1)^r-(n + 1) = {r\choose 1}S_{1} + {r\choose 2}S_{2} + \cdots + {r\choose r-1}S_{r-1}$$