Page 184 - Discrete Mathematics and Its Applications

2.4 Sequences and Summations 163

from the sequence {a n }. We use the notation

n

n
a j , j= m j , or m≤j≤n j
a
a
j= m
(read as the sum from j = m to j = n of a j ) to represent
a m + a m+1 + ··· + a n .

Here, the variable j is called the index of summation, and the choice of the letter j as the
variable is arbitrary; that is, we could have used any other letter, such as i or k. Or, in notation,

n n n

a j = a i = a k .
j=m i=m k=m

Here, the index of summation runs through all integers starting with its lower limit m and ending

with its upper limit n. A large uppercase Greek letter sigma, , is used to denote summation.
The usual laws for arithmetic apply to summations. For example, when a and b are real
n n n
y
x
numbers, we have (ax j + by j ) = a y=1 j + b j=1 j , where x 1 ,x 2 ,...,x n and
j=1
y 1 ,y 2 ,...,y n are real numbers. (We do not present a formal proof of this identity here. Such a
proof can be constructed using mathematical induction, a proof method we introduce in Chap-
ter 5. The proof also uses the commutative and associative laws for addition and the distributive
law of multiplication over addition.)
We give some examples of summation notation.
EXAMPLE 17 Use summation notation to express the sum of the first 100 terms of the sequence {a j }, where
a j = 1/j for j = 1, 2, 3,....

Solution: The lower limit for the index of summation is 1, and the upper limit is 100. We write
this sum as

100
1
.
j ▲
j=1

NEIL SLOANE (BORN 1939) Neil Sloane studied mathematics and electrical engineering at the Uni-
versity of Melbourne on a scholarship from the Australian state telephone company. He mastered many
telephone-related jobs, such as erecting telephone poles, in his summer work. After graduating, he designed
minimal-cost telephone networks in Australia. In 1962 he came to the United States and studied electri-
cal engineering at Cornell University. His Ph.D. thesis was on what are now called neural networks. He
took a job at Bell Labs in 1969, working in many areas, including network design, coding theory, and
sphere packing. He now works for AT&T Labs, moving there from Bell Labs when AT&T split up in
1996. One of his favorite problems is the kissing problem (a name he coined), which asks how many
spheres can be arranged in n dimensions so that they all touch a central sphere of the same size. (In two
dimensions the answer is 6, because 6 pennies can be placed so that they touch a central penny. In three dimensions, 12 billiard
balls can be placed so that they touch a central billiard ball. Two billiard balls that just touch are said to “kiss,” giving rise to the
terminology “kissing problem” and “kissing number.”) Sloane, together with Andrew Odlyzko, showed that in 8 and 24 dimensions,
the optimal kissing numbers are, respectively, 240 and 196,560. The kissing number is known in dimensions 1, 2, 3, 4, 8, and 24, but
not in any other dimensions. Sloane’s books include Sphere Packings, Lattices and Groups, 3d ed., with John Conway; The Theory
of Error-Correcting Codes with Jessie MacWilliams; The Encyclopedia of Integer Sequences with Simon Plouffe (which has grown
into the famous OEIS website); and The Rock-Climbing Guide to New Jersey Crags with Paul Nick. The last book demonstrates his
interest in rock climbing; it includes more than 50 climbing sites in New Jersey.