Page 188 - Discrete Mathematics and Its Applications

2.4 Sequences and Summations 167

SOME INFINITE SERIES Although most of the summations in this book are finite sums,
infinite series are important in some parts of discrete mathematics. Infinite series are usually
studied in a course in calculus and even the definition of these series requires the use of calculus,
but sometimes they arise in discrete mathematics, because discrete mathematics deals with infi-
nite collections of discrete elements. In particular, in our future studies in discrete mathematics,
we will find the closed forms for the infinite series in Examples 24 and 25 to be quite useful.
∞ n
EXAMPLE 24 (Requires calculus) Let x be a real number with |x| < 1. Find n = 0 x .

x k+1 − 1
k n
Solution: By Theorem 1 with a = 1 and r = x we see that x = . Because
n = 0
x − 1
|x| < 1, x k+1 approaches 0 as k approaches infinity. It follows that
∞ k+1
n x − 1 0 − 1 1
x = lim = = . ▲
k→∞ x − 1 x − 1 1 − x
n = 0
Wecanproducenewsummationformulaebydifferentiatingorintegratingexistingformulae.
EXAMPLE 25 (Requires calculus) Differentiating both sides of the equation

∞
1
k
x = ,
1 − x
k = 0
from Example 24 we find that
∞
k−1 1
kx = .
(1 − x) 2
k = 1
(This differentiation is valid for |x| < 1 by a theorem about infinite series.) ▲
Exercises

1. Find these terms of the sequence {a n }, where a n = d) the sequence whose nth term is n!− 2 n
n
n
2 · (−3) + 5 . e) the sequence that begins with 3, where each succeed-
a) a 0 b) a 1 c) a 4 d) a 5 ing term is twice the preceding term
2. What is the term a 8 of the sequence {a n } if a n equals f) the sequence whose first term is 2, second term is 4,
a) 2 n−1 ? b) 7? and each succeeding term is the sum of the two pre-
n
n
c) 1 + (−1) ? d) −(−2) ? ceding terms
3. What are the terms a 0 , a 1 , a 2 , and a 3 of the sequence {a n }, g) the sequence whose nth term is the number of bits
where a n equals in the binary expansion of the number n (defined in
n
a) 2 + 1? b) (n + 1) n+1 ? Section 4.2)
c) n/2 ? d) n/2 + n/2 ? h) the sequence where the nth term is the number of let-
ters in the English word for the index n
4. What are the terms a 0 , a 1 , a 2 , and a 3 of the sequence {a n },
where a n equals 6. List the first 10 terms of each of these sequences.
n
a) (−2) ? b) 3? a) the sequence obtained by starting with 10 and obtain-
n
n
n
c) 7 + 4 ? d) 2 + (−2) ? ing each term by subtracting 3 from the previous term
5. List the first 10 terms of each of these sequences. b) the sequence whose nth term is the sum of the first n
positive integers
a) the sequence that begins with 2 and in which each n n
successive term is 3 more than the preceding term c) the sequence whose nth term is 3 − 2
√
b) the sequence that lists each positive integer three d) the sequence whose nth term is n
times, in increasing order e) the sequence whose first two terms are 1 and 5 and
c) the sequence that lists the odd positive integers in in- each succeeding term is the sum of the two previous
creasing order, listing each odd integer twice terms