Mathematics for Computer Science

Chapter 13 Sums and Asymptotics526

outer sum (which no longer has a summation inside it). For example,^5

X^1

nD 0

yn

Xn

iD 0

xi

!

D

X^1

nD 0



yn

1 xnC^1

1 x



equation 13.2

D



1

1 x

X 1

nD 0

yn



1

1 x

X 1

nD 0

ynxnC^1

D

1

.1x/.1y/

 x

1 x

X^1

nD 0

.xy/n Theorem 13.1.1

D

1

.1x/.1y/

x

.1x/.1xy/

Theorem 13.1.1

D

. 1 xy/x.1y/
.1x/.1y/.1xy/

D

1 x

.1x/.1y/.1xy/

D

1

.1y/.1xy/

:

When there’s no obvious closed form for the inner sum, a special trick that is
often useful is to tryexchanging the order of summation.For example, suppose we
want to compute the sum of the firstnharmonic numbers

Xn

kD 1

HkD

Xn

kD 1

Xk

jD 1

1

j

(13.26)

For intuition about this sum, we can apply Theorem 13.3.2 to equation 13.20 to
conclude that the sum is close to
Zn

1

ln.x/dxDxln.x/x

ˇ

ˇˇn

1

Dnln.n/nC1:

Now let’s look for an exact answer. If we think about the pairs.k;j/over which

(^5) OK, so maybe this one is a little hairy, but it is also fairly straightforward. Wait till you see the
next one!