Transcript Section 3.2: Sequences and Summations

Section 3.2: Sequences and
Summations
Def: A sequence is a function from a subset of the set of integers
(usually the set of natural numbers) to a set S. We use the notation ak
to denote the image of the integer k.
Ex: Consider the sequence 1, 2, 3, 4, 5, 6, … We could specify this
sequence as {ak} where ak = k + 1 and the sequence is indexed with
the set of natural numbers. That is, a0 = 1, a1 = 2, a2 = 3, … Note the
overloaded use of {}; they do not indicate a set here but a sequence.
We will be careful to indicate that we are dealing with a sequence
when specifying them in this manner to avoid confusion with sets.
Ex: The digits in a real number comprise a sequence. Consider .
 = 3.14159265… We can consider the digits after the decimal point
as a sequence indexed by the set of natural numbers {pk}. So p0 = 1,
p1 = 4, p2 = 1, p3 = 5, p4 = 9, p5 = 2, and so on.
Any real number can be considered in this manner [before the decimal
must be an integer, after the decimal though is a sequence of digits].
Ex: 376.1111… is a real number. To the left of the decimal we have
an integer, 376, but to the right we have an infinite sequence of digits.
This sequence is specified as {ak} where ak = 1 for all k  N.
Ex: 1/2 = 0.5 is a real number. To the left of the decimal we have an
integer, 0, and to the right we have a sequence of digits. This
sequence only has one digit so we could index the sequence by the
subset of the integers {0}. And then a0 = 5. However we can consider
a real number to always have a sequence of digits indexed by the set
of natural numbers at its end if we wish. If the decimal terminates, we
simply extend it with 0s. That is 1/2 = 0.5000… and our sequence of
digits is now {ak} where a0 = 5 and ak = 0 for all k > 0.
Ex: Consider the sequence {ak} where ak = 1/(k + 1) for all k  N.
Then the terms of this sequence are 1, 1/2, 1/3, 1/4, 1/5, … Note that
this is a sequence of rational numbers. We have dealt with numbers up
to this point in our examples but remember that the set S from which
our elements are chosen is arbitrary.
Def: A geometric progression is a sequence of the general form
a, ar, ar2, ar3, …
where the initial term a and the common ratio r are real numbers.
Ex: The sequence {bk} with bk = (-1)k indexed by the set of natural
numbers is a geometric progression with initial term 1 and common
ratio -1. We can see that b0 = (-1)0 = 1, b1 = (-1)1 = -1, b2 = (-1)2 = 1,
and so on. So the terms of this sequence are 1, -1, 1, -1, ...
Ex: The sequence {ck} with ck = 2(5)k indexed by the set of natural
numbers is a geometric progression with initial term 2 and common
ratio 5. We can see that c0 = 2(5)0 = 2, c1 = 2(5)1 = 10, c2 = 2(5)2 =
50, and so on. So the terms of this sequence are 2, 10, 50, 250, ...
Def: An arithmetic progression is a sequence of the general form
a, a + d, a + 2d, a + 3d, …
where the initial term a and the common difference d are real numbers.
Ex: The sequence {bk} with bk = 1 + 4k indexed by the set of natural
numbers is an arithmetic progression with initial term 1 and common
difference 4. We can see that b0 = 1 + 4*0 = 1, b1 = 1 + 4*1 = 5, b2 = 1
+ 4*2 = 9, and so on. So the terms of this sequence are 1, 5, 9, 13, ...
Ex: The sequence {ck} with ck = -1 + (1/2)k indexed by the set of
natural numbers is an arithmetic progression with initial term -1 and
common difference 1/2. We can see that c0 = -1 + (1/2)0 = -1, c1 = -1
+ (1/2)1 = -1/2, c2 = -1 + (1/2)2 = 0, and so on. So the terms of this
sequence are -1, -1/2, 0, 1/2, 1, ...
Def: A string is a sequence which is indexed by a finite subset of the
integers. The length of the string is the cardinality of the indexing set.
Ex: 101011 is a string of bits (a.k.a. bit string) of length 6.
Summations
Sometimes when we have a sequence of numbers {ak} we would like
to sum the terms of the sequence. That is, we would like to find the
sum a0 + a1 + a2 + … We have a special notation for this sum:
ak = a0 + a1 + a2 + …
We also would like to specify the sum of the terms of a sequence in a
particular range:
nj = m aj = am + am+1 + …+ an. [We sum all aj where m  j  n]
In the above notation j is called the index of summation, m is called
the lower limit and n is called the upper limit.
Ex: 99j = 0 1/(j + 1) represents the sum of the first 100 terms of our
example sequence {ak} where ak = 1/(k + 1).
Ex: 5j = 1 j2 = 12 + 22 + 32 + 42 + 52 = 1 + 4 + 9 + 16 + 25 = 55
Identity: Let {aj} be a sequence of real numbers. Then
nj = m aj + nj = m bj = nj = m (aj + bj)
To take advantage of the above identity, we often need to shift the index
in a summation:
Ex: 5j = 1 j2 + 4k = 0 2k = 5j = 1 j2 + 5r = 1 2(r – 1) = 5j = 1 j2 + 2(j – 1)
= 5j = 1 (j2 + 2j – 2) = (12 + 2*1 – 2) + (22 + 2*2 – 2) + (32 + 2*3 – 2) +
(42 + 2*4 – 2) + (52 + 2*5 – 2) = 1 + 6 + 13 + 22 + 33 = 75
Identity: Let a and r be real numbers with r  0. Then
nj = 0 arj = (arn+1 – a)/(r – 1) if r  1. [If r = 1, then (n + 1)a is the sum.]
There is a table of useful summation formulas (including the above) in
the text on page 232. [See also the discussion of how to evaluate nested
sums].
Cardinality
Recall that the cardinality of a set S was defined to be the number
of elements in the set S. Two finite sets have the same cardinality
if they have the same number of elements. The following
definition extends the concept of cardinality.
Def: The sets A and B have the same cardinality if and only if
there is a one-to-one correspondence from A to B.
Remark: Recall that we pointed out the “if” part of this definition
for finite sets when we studied functions. That is, we remarked
that if the sets A and B have finite cardinality, then a function
from A to B can be one-to-one only if |A|  |B|. And a function
from A to B can only be onto if |A|  |B|. Taken together, we
realized that for finite sets A and B, a function from A to B could
be a one-to-one correspondence only if |A| = |B|.
So we just verified that the given definition doesn’t contradict our
earlier treatment of finite sets. This may not seem like the most
natural definition for cardinality at first, but upon further examination
it turns out to be very natural. [What do we do when we count?].
When we count the elements of a finite set, we are forming a one-toone correspondence with the subset {1, 2, …, n} of the set of integers.
Once we have formed this one-to-one correspondence, we conclude
that the set we counted has cardinality n.
Using this notion of cardinality, we can begin to compare the cardinality
of infinite sets as well. Some infinite sets seem to be bigger than other
infinite sets, but it turns out that they have the same cardinality.
Ex: We know that Z+  N. That is N has every positive integer in it,
but in addition it has 0 which Z+ does not. So it seems that N is ‘bigger’
than Z+. But consider f: N  Z+ defined by f(n) = n + 1. This function
f is a one-to-one correspondence between N and Z+. So |N| = |Z+|.
Def: A set that has finite cardinality or has the same cardinality as the
positive integers is called countable. A set that is not countable is
called uncountable.
Ex: We just saw that the set of natural numbers is countable.
Remark: An infinite set S is countable if and only if it is possible to
list all of the elements of S in a sequence (indexed by Z+).
Remember that a sequence of elements from S indexed by Z+ is a
function f: Z+  S. The requirement that it is possible to list all of the
elements of S in a sequence means that there exists such a function f
from Z+ to S which is onto. And if we can have such an onto
function, we can make sure it is also one-to-one by keeping only the
first occurrence of each element of S in the sequence.
Ex: The set of integers is countable because we can list all of the
integers in a sequence: 0, -1, 1, -2, 2, -3, 3, -4, …
The bijection is f(x) = (x – 1)/2 for odd x, and f(x) = -x/2 for even x.
Ex: The set Z  Z is countable.
We use the technique of exhaustively listing the members of this set
in a sequence. Once again, the order of listing is important. [Graph]
(0, 0), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1), (2, -1),
(2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (-1, 2), (-2, 2), (-2, 1), (-2, 0), …
This is not the only possibility. For another example, we could have
organized our listing by distance from the origin:
0: (0, 0)
1: (1, 0), (0, 1), (-1, 0), (0, -1)
2: (2, 0), (1, 1), (0, 2), (-1, 1), (-2, 0), (-1, -1), (0, -2), (1, -1)
…
Theorem: A subset of a countable set is countable.
Corollary: The set of rational numbers is countable.
Test 2
• In class, Wednesday, April 2
– Send me email to arrange to take the test on an
earlier date if you can not take it on April 2
• Sections 1.8, 2.4, 3.1, 3.2, 3.3, and 3.4
• HW5, HW6 (due 3-24), HW7(will be due 3-31)
Theorem: The set of real numbers is uncountable.
Remark: Up to this point we have only proven sets to be countable.
To prove that an infinite set is countable, we only had to find a
bijection between it and the set of positive integers. This sort of thing
is an existence proof. However, to prove that a set is uncountable, we
must show that there does not exist any bijection between it and the set
of positive integers. This is significantly harder.
Before we proceed with the proof, recall what a real number is. All
real numbers take the form
x.d1d2d3…
where x is an integer (hence finite) and the thing to the right of the
decimal point is a sequence of digits indexed by the set of positive
integers. Remember that even real numbers with a decimal that
terminates (like 5.725) can still be thought of in this manner. We just
tack on 0’s at the end (5.725000…).
Proof: Assume, to the contrary, that the set of real numbers is countable.
Then the subset of the real numbers B = {x | 0 < x < 1} is also countable
(since a subset of a countable set is countable).
So there exists a bijection from the set of positive integers to B (call it f).
We don’t know anything about f other than it is a bijection from Z+ to B.
f(1) = 0.d11d12d13…,
f(2) = 0.d21d22d33…,
f(3) = 0.d31d32d33…, etc.
Since f is a bijection (and hence onto) then every real number in B must
appear somewhere on this list (as f(n) for some positive integer n).
Consider the member 0.d1d2d3… of B where each digit di = 4 if dii  4
and di = 5 if dii = 4. This member of B can not appear as f(n) for any
positive integer n since the nth digit (dn) of this number differs from the
nth digit (dnn) of f(n). Hence this is a member of B which is not mapped
to by any positive integer n. So f is not onto. So R is uncountable.
What we just did was to show that B must be uncountable because any
function from Z+ to B that you propose to me as a bijection can’t be
onto. We did this by taking the proposed bijection and constructing a
number in B that is not mapped to by any integer. So no such bijection
exists because any one that is proposed can be shown to not be onto.
The technique used in this proof is called diagonalization (we went
down the diagonal to assign our digits for the number we created). This
technique can be used to prove that many other sets are uncountable.
Once you understand this diagonalization argument from the previous
proof, consider the following question:
We know that the set of natural numbers is countable because we found
a bijection between it and the positive integers. Hence we shouldn’t be
able to prove that the set of natural numbers is uncountable (because it
isn’t). We could tack on zeros to the front of any natural number
leaving its value unchanged, just as we did at the end of real numbers.
Why then can we not use this diagonalization technique to show that
the set of natural numbers is uncountable?