Page 186 - Discrete Mathematics and Its Applications

2.4 Sequences and Summations 165

To compute S, first multiply both sides of the equality by r and then manipulate the resulting
sum as follows:
n
j
rS n = r ar substituting summation formula for S
j=0
n

= ar j+1 by the distributive property
j=0
n+1
k
= ar shifting the index of summation, with k = j + 1
k=1
n

k
= ar + (ar n+1 − a) removing k = n + 1 term and adding k = 0 term
k=0
= S n + (ar n+1 − a) substituting S for summation formula

From these equalities, we see that

rS n = S n + (ar n+1 − a).

Solving for S n shows that if r = 1, then

ar n+1 − a
S n = .
r − 1
n j n
If r = 1, then the S n = ar = a = (n + 1)a.
j=0 j=0
EXAMPLE 21 Double summations arise in many contexts (as in the analysis of nested loops in computer
programs). An example of a double summation is

4 3

ij.
i=1 j=1

To evaluate the double sum, first expand the inner summation and then continue by computing
the outer summation:

4 3 4

ij = (i + 2i + 3i)
i=1 j=1 i=1
4

= 6i
i=1
▲
= 6 + 12 + 18 + 24 = 60.
We can also use summation notation to add all values of a function, or terms of an indexed
set, where the index of summation runs over all values in a set. That is, we write

f(s)
s ∈ S

to represent the sum of the values f(s), for all members s of S.