Sequences
Sequences represent ordered lists of elements.
A sequence is defined as a function from a subset of
N to a set S. We use the notation an to denote the
image of the integer n. We call an a term of the
sequence.
Example:
subset of N: 1 2 3 4 5 …
S: 2 4 6 8 10 …
February 7, 2013 Applied Discrete Mathematics 1
Week 2: Functions and Sequences
Sequences
We use the notation {an} to describe a sequence.
Important: Do not confuse this with the {} used in set
notation.
It is convenient to describe a sequence with an
equation.
For example, the sequence on the previous slide
can be specified as {an}, where an = 2n.
February 7, 2013 Applied Discrete Mathematics 2
Week 2: Functions and Sequences
The Equation Game
What are the equations that describe the
following sequences a1, a2, a3, … ?
1, 3, 5, 7, 9, … an = 2n - 1
-1, 1, -1, 1, -1, … an = (-1)n
2, 5, 10, 17, 26, … an = n2 + 1
0.25, 0.5, 0.75, 1, 1.25 … an = 0.25n
3, 9, 27, 81, 243, … an = 3n
February 7, 2013 Applied Discrete Mathematics 3
Week 2: Functions and Sequences
Strings
Finite sequences are also called strings, denoted
by a1a2a3…an.
The length of a string S is the number of terms that
it consists of.
The empty string contains no terms at all. It has
length zero.
February 7, 2013 Applied Discrete Mathematics 4
Week 2: Functions and Sequences
Summations
n
What does åa
j =m
j stand for?
It represents the sum am + am+1 + am+2 + … + an.
The variable j is called the index of summation,
running from its lower limit m to its upper limit n.
We could as well have used any other letter to
denote this index.
February 7, 2013 Applied Discrete Mathematics 5
Week 2: Functions and Sequences
Summations
How can we express the sum of the first 1000
terms of the sequence {an} with an=n2 for
n = 1, 2, 3, … ?
1000
We write it as å
j =1
j 2.
6
What is the value of åj?
j =1
It is 1 + 2 + 3 + 4 + 5 + 6 = 21.
100
What is the value of åj?
j =1
It is so much work to calculate this…
February 7, 2013 Applied Discrete Mathematics 6
Week 2: Functions and Sequences
Summations
It is said that Carl Friedrich Gauss came up with the
following formula:
n
n( n + 1)
åj =1
j=
2
When you have such a formula, the result of any
summation can be calculated much more easily, for
example:
100
100(100 + 1) 10100
åj =1
j=
2
=
2
= 5050
February 7, 2013 Applied Discrete Mathematics 7
Week 2: Functions and Sequences
Double Summations
Corresponding to nested loops in C or Java,
there is also double (or triple etc.) summation:
Example:
5 2
åå ij
i =1 j =1
5
= å (i + 2i )
i =1
5
= å 3i
i =1
= 3 + 6 + 9 + 12 + 15 = 45
February 7, 2013 Applied Discrete Mathematics 8
Week 2: Functions and Sequences
Double Summations
Corresponding to nested loops in C or Java,
there is also double (or triple etc.) summation:
Example:
1. Sum of 2i for i=50 to 100
2. Convert loop to summation and vice versa.
February 7, 2013 Applied Discrete Mathematics 9
Week 2: Functions and Sequences
