Page 187 - Discrete Mathematics and Its Applications

166 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

TABLE 2 Some Useful Summation Formulae.
Sum Closed Form
n
k ar n+1 − a
ar (r = 0) ,r = 1
r − 1
k = 0
n
n(n + 1)
k
2
k = 1
n
2 n(n + 1)(2n + 1)
k
6
k = 1
n
2
3 n (n + 1) 2
k
4
k = 1
∞
k 1
x , |x| < 1
1 − x
k = 0
∞
k−1 1
kx , |x| < 1
(1 − x) 2
k = 1
EXAMPLE 22 What is the value of s?
s ∈{0,2,4}

Solution: Because s represents the sum of the values of s for all the members of the
s ∈{0,2,4}
set {0, 2, 4}, it follows that

s = 0 + 2 + 4 = 6.
▲
s ∈{0,2,4}
Certain sums arise repeatedly throughout discrete mathematics. Having a collection of
formulae for such sums can be useful; Table 2 provides a small table of formulae for commonly
occurring sums.
We derived the first formula in this table in Theorem 1. The next three formulae give us the
sum of the first n positive integers, the sum of their squares, and the sum of their cubes. These
three formulae can be derived in many different ways (for example, see Exercises 37 and 38).
Also note that each of these formulae, once known, can easily be proved using mathematical
induction, the subject of Section 5.1. The last two formulae in the table involve infinite series
and will be discussed shortly.
Example 23 illustrates how the formulae in Table 2 can be useful.

2
EXAMPLE 23 Find 100 k .
k = 50
100 2 49 2 100 2
Solution: First note that because k = k + k ,wehave
k = 1 k = 1 k = 50
100 100 49

2 2 2
k = k − k .
k = 50 k = 1 k = 1
n 2
Using the formula k = n(n + 1)(2n + 1)/6 from Table 2 (and proved in Exercise 38),
k = 1
we see that
100
100 · 101 · 201 49 · 50 · 99
2
k = − = 338,350 − 40,425 = 297,925. ▲
6 6
k = 50