Mathematics for Computer Science

Chapter 14 Sums and Asymptotics430

we are summing, they form a triangle:

j

1 2 3 4 5 ::: n

k 1 1

2 1 1=2

3 1 1=2 1=3

4 1 1=2 1=3 1=4

:::

n 1 1=2 ::: 1=n

The summation in equation 14.31 is summing each row and then adding the row

sums. Instead, we can sum the columns and then add the column sums. Inspecting

the table we see that this double sum can be written as

Xn

kD 1

HkD

Xn

kD 1

Xk

jD 1

1

j

D

Xn

jD 1

Xn

kDj

1

j

D

Xn

jD 1

1

j

Xn

kDj

1

D

Xn

jD 1

1

j

.njC1/

D

Xn

jD 1

nC 1

j

Xn

jD 1

j

j

D.nC1/

Xn

jD 1

1

j

Xn

jD 1

1

D.nC1/Hnn: (14.32)