Telescoping Sums

1

Sums

Telescoping

At

Looking

by Titu Andreescu Illinois Mathematics and Science Academy

Sums as n

n

∑

∑ai + 1 - ai 

[F(k) - F(k - 1)] or

k=1

i=1

are called "telescopic " or "collapsing " sums, because most of the terms cancel out. For instance, if n = 19, 19 ∑ [F(k) - F(k - 1)] = F(1) - F(0) + F(2) - F(1) + F(3) - F(2) + ... + F(19) - F(18) = F(19) k=1 F(0), because F(1) and -F(1), F(2) and -F(2), . . . , F(18) and -F(18) cancel out, and for n = 92 92  a - a  = a - a + a - a + a - a + . . . + a - a = a - a ,

∑

i +1

i

2

1

3

2

k=1 because a and -a , a and -a , . . . , a 2

2

3

3

92

4

3

and -a

92

93

92

93

1

collapse.

The Telescoping Sums Theorem (or Fundamental Theorem of Summation) states that: n

∑ [F(k) - F(k - 1)]

= F(n) - F(0)

k=1 or, respectively, n

∑ ai + 1 - ai = an + 1 -

a

1

.

i=1

By choosing F(k) or a appropriately one can compute several important sums.

i

For example, let's take into consideration:

n

∑

k .

k=1

2 Using the identity k2 - (k - 1)2 = 2k - 1 and the Telescoping Sums Theorem for F(k) = k2 n n n n we get: n2 - 02 = ∑ [k2 - (k - 1)2] = ∑ (2k - 1) = 2 ∑ k - ∑ 1 , k=1

k=1

k=1

k=1

whence n

n

2

∑

k - n = n2 ,

∑

i.e.

k=1

k=

n(n + 1) (1) 2

k=1

Similarly, using the identity (i + 1)3 - i 3 = 3i 2 + 3i + 1 and the Telescoping Sums Theorem for a = i 3 we obtain: i

n

(n + 1)3 - 1 =

∑

[(i + 1)3 - i 3] =

n

∑ (3i 2 + 3i + 1)

=

i=1

i=1 n

∑i

3

2 +3

i=1

n

∑i

n

+

i=1

whence n

3

∑ i 2 = (n + 1)3 - 1 - 3n(n2 + 1)

∑

1

n

(1)

3

∑i2

+

3n(n + 1) +n, 2

i=1

i=1

- n = (n + 1)3 -

3n(n+1) - (n + 1) = 2

i=1 3n 2n2 + n   (n + 1)  (n + 1)2 - 2 - 1 = (n + 1) 2 n

∑i2

i.e.

=

n(n + 1)(2n + 1) 6

i=1 n

In many situations where we are asked to evaluate

b as a k

k+1

∑ bk , we will try to express

k=1 - a in order to apply the Telescoping Sums Theorem. This will give us: k

n

n

∑

b

k=1

k

=

∑ak + 1 - ak k=1

= a

n+1

- a . 1

3 n

∑

For example one can compute

k!•k by writing b = k! • k as k!•(k + 1 - 1) = k

k=1 k!•(k + 1) - k! = (k + 1)! - k! = a - a where a = k!. Hence k+ 1

k

n

n

∑ 1

=

4k2 - 1

n

∑

∑

n

1 = (2k - 1)(2k + 1)

∑

n

 1 - 1  =-1  2k - 1 2k + 1 2

∑

1 2

•

(2k + 1) - (2k - 1) (2k - 1)(2k + 1)

k=1

k=1

k=1 1 =2

[(k + 1)! - k!] = (n + 1)! - 1 .

k=1 n

n

∑

∑

k!•k =

k=1 In the same way

k

 1 - 1  =-1  2k + 1 2k - 1 2

n

∑ ak + 1 - ak

k=1 k=1 k=1 1 1  = - 2  a - a  by the Telescoping Sums Theorem  here a = k 2k - 1 n+1 1 n 1  1 n 1  = - 2  2n + 1 - 1 = 2n + 1 Therefore, 2 4k - 1

∑

k=1

More generally, if x , x , . . . , x is an arithmetical sequence, we may compute in a 1

2

n

n

similar way:

∑

1 x x

k k+1

k=1 Let d be the common difference. Then x

∑

1 x x

=

k k+1

∑

d 1 d •x x

∑ k=1

n

1 = d

k k+1

1 =d

k=1

k=1

- x = d, k = 1, 2, . . . , n - 1, so:

∑ k=1

k

n

n

n

k+1

1 1 + x   x  k +1 k

x

k +1

x x

-x

k

k k+1

n

1 =d

∑ k=1

x - x 1 1 n+1 1 + x  = d • x x n +1 1 1 n+1

1 1 d  - x

1 - 1  x   k xk + 1

4 x + nd - x 1 1 1 1 nd =d • = d •x x x x 1 n+1

1 n+1

n =x x

1 n+1

For x = 2k - 1 we find the previous result: k

n

∑

n 1 = 1• (1 + 2 • n) (2k - 1)(2k + 1)

k=1

(*) We applied the Telescoping Sums Theorem for F(k) = - x

1

k+1

For an arithmetical sequence x , x , . . . , x , the sum 1

2

n

n

∑

1 x x

x

k k+1 k+2

k=1 can also be computed by using the Telescoping Sums Theorem .

If d is the common difference, then x

k+2

- x = 2d, k = 1, 2, . . . , n, k

so 1 = 2d

1 x x

x

k k+1 k+2

•

2d x x x

k k+1 k+2

1 = 2d

•

x

-x

x x

x

k+2

k

k k+1 k+2

1 = 2d

therefore n

n

∑

1 x x

k k+1 k+2

1 = 2d

•

∑ k=1

k=1 1 2d

x

1 1  + x x  = x x  n+1 n+2 1 2

• -

1 1 -  - x x    x x  k+1 k+2  k k+1  

•

1  1 - x x  , x x  k k+1 k+1 k+2 

5

1 2d

1 2d

(**)

-x x +x 1 2

•

x

n+1 n+2

x x x

x

1 2 n+1 n+2

2nx d + n(n+1)d2 1

•

x x x

x

1 2 n+1 n+2

1 = 2d

1 =2

•

- x  x + d +  x + nd  x + (n+1)d   1  1  1 1 = x x x x 1 2 n+1 n+2

n 2x + (n+1)d x +x  1  n  1 n+2  n 1  1 • = 2  x x x x  = 2x x x + x  x x x x  1 2 n+1 n+2 2 n+1  1 n+2 1 2 n+1 n+2

1 We applied the Telescoping Sums Theorem for F(k) = - x x

.

k k+1

Using the Telescoping Sums Theorem one can solve more intricate problems as: 1 1 1 cos 1˚ cos0˚cos1˚ + cos1˚cos2˚ + . . . + cos 88˚cos89˚ = sin21˚ (21st United States of America Mathematical Olympiad)

Prove:

Indeed, multiplying the relation above the sin 1˚ we get: sin 1˚ sin 1˚ sin 1˚ + cos 1˚cos 2˚ + . . . + cos 88˚ cos 89˚ cos 0˚cos 1˚

cos 1˚ = sin 1˚

or sin (1˚- 0˚) cos 1˚ cos 0˚

sin (2˚- 1˚) sin (89˚- 88˚) + cos 2˚ cos 1˚ + . . . + cos 89˚ cos 88˚ = cot 1˚

i.e. 89

∑

sin [k° - (k - 1)°] = tan 89˚ cos k° cos (k - 1)°

k=1 which by the identity: sin(a - b) cos a cos b = tan a - tan b is 89

∑ [tan k˚ - tan(k - 1)˚]

= tan 89˚ - tan 0˚

k=1 i.e

Telescopic Sums Theorem for F(k) = tan k˚ and n = 89.

In conclusion, I invite the readers to compute the following sums:

6 n

a)

∑

k3 ,

b)

∑

∑

n

∑

k4 ,

k5 .

k=1

k=1

k=1 n

n

k!•(k2 + k + 1) .

k=1 n

c)

∑

x x

1 x

x

k k+1 k+2 k+3

where x , x , . . . , x is an arithmetical sequence. 1

2

n

k=1 d)

1 1 1 + + ...+ sin 2˚ sin 3˚ sin 178˚ sin 179˚ . ✍ sin 1˚ sin 2˚