Discrete Structures

# Sequences & Summations:

## Further Information

 Last Update: 25 March 2009 Note: or material is highlighted

1. A sequence (a) is the output (i.e., the range) of a function whose input (i.e., whose domain) is either the set of positive integers (Z+ = {1,2,3,…}) or the set of natural numbers (N = {0,1,2,3,…}),
depending on whether it's more convenient to begin counting with 1 or 0,
and (b) is such that the output is ordered by the input (i.e., it's like an ordered ∞-tuple; it's not an unordered set).

The name of the function is often "a", and, instead of writing the outputs as a(0), a(1), a(2), etc., they are often written using subscripts:

a0, a1, a2, …, an, an+1, …

Here are a couple of examples:

1. 0, 1, 4, 9, 16, 25, …

This is a sequence where

a0 = 0
a1 = 1
a2 = 4
a3 = 9
a4 = 16
a5 = 25, etc.

It can be described as follows:

an = n2, for all n

2. 0, 1, 1, 2, 3, 5, 8, 13, …

This is a sequence where

a0 = 0
a1 = 1
a2 = 1
a3 = 2
a4 = 3
a5 = 5
a6 = 8
a7 = 13, etc.

It can be described as follows:

a0 = 0
a1 = 1
an = an–1 + an–2, for all n > 1

In other words, the first term of the sequence is 0, the next is 1, and each one afterwards is the sum of the two preceding terms.

It's a famous sequence that we'll see again, called the Fibonacci (pronounced "fib-o-NAH-tchi") sequence.
(By the way, some people start it at a1, not a0; it can also be continued backwards to a–1a–2, etc.
You might want to try to figure out what those terms of the sequence would be.)

SAT/IQ-test questions often give you a sequence and ask you what "the" next member is.
But there is no such thing as "the" next member! Any number could be the next member.
In other words, there's nothing wrong with a sequence described as follows:

a0 = 0
a1 = 1
a2 = 2
a3 = 3
a4 = 4
a5 = 5

Do you think a6 = 6? It might. But I could continue as follows if I want to be perverse:

an = 27n, for all n such that 5 < n < 123
an = 3, for all n > 123

I.e., the sequence is:

0, 1, 2, 3, 4, 5, 276, 277, 278, …, 27122, 3, 3, …

That's a weird, uninteresting sequence, but it is a sequence.

Douglas Hofstadter, author of one of the best books on computation and cognition
(it won the Pulitzer Prize for non-fiction when it was published)—Gödel, Escher, Bach: An Eternal Golden Braid
has done a lot of computational research on how to get computers to figure out plausible "next" members of sequences,
in a book called Fluid Concepts and Creative Analogies.

And don't forget to check out The On-Line Encyclopedia of Integer Sequences and one of my favorite sequences:

1, 11, 111, 15, 5, 51, 511, 5111, 110, 10, 101, 1011, 10111, 1015, 105, …

2. Summations are simply the sums of the terms in a sequence.
Some people call them "series" instead of summations (I've never figured out why).
I.e., a summation is, by definition, the sum of some or all terms in a sequence.
So, given the sequence

a1, a2, …, an, …,

the corresponding summation is

a1 + a2 + … + an + …

You'd think that this would have to be a very large number
(after all, you keep adding more and more numbers),
and it often is quite large,
but sometimes such a summation "converges" to a finite number
and turns out to be a convenient way to compute the number that is the sum.

For instance, consider this sequence:

1, –1/3, 1/5, –1/7, 1/9, …

where:

if Odd(n), then an = +1/(2n–1)
else an = –1/(2n–1)

Check it out:

Odd(1), so a1 = 1/(2*1 – 1) = 1/(2–1) = 1/1 = 1

Even(2), so a2 = –1/(2*2 – 1) = –1/(4–1) = –1/3

etc.

Now consider its summation:

1 + –1/3 + 1/5 + –1/7 + 1/9 + …

=  1 – 1/3 + 1/5 – 1/7 + 1/9 – …

As you might guess, this converges (i.e., it does not get infinitely large).
After all, each time we're adding on a smaller fraction, and some of them are negative, so we're actually subtracting them.
All of that will surely make each successive "partial" sum only a very little bit bigger than the previous some, and in some cases, it'll be smaller.

Let's compute the partial sums:

The sum of the first term is just 1.
The sum of the first 2 terms is 1 – 1/3 = 2/3 = 0.666666666666666666…
The sum of the first 3 terms is 1 – 1/3 + 1/5 = 0.66… + 0.2 = 0.8666…
The sum of the first 4 terms is 1 – 1/3 + 1/5 – 1/7 = 0.866… – 0.1428571… = 0.723809523…
The sum of the first 5 terms is 0.723809523… + 1/9 = 0.723809523… + 0.11111… = 0.834920634…

etc.

It turns out (and I won't ask you to prove this!) that the sum of the infinite sequence is (get ready… drum roll, please):

π/4 (!)

(Consider what happens when you multiply each term in the summation by 4:

4 – 4/3 + 4/5 – 4/7 + 4/9 – …

The partial sum of these first 5 terms is 3.33968253…; it's getting close to π.)

So, you could write a computer program to compute π to any degree of accuracy
(i.e., to any position in the decimal expansion of π)
by writing a for-loop (or a "count-loop") that adds up these numbers.

It doesn't always happen that a series like this converges. Consider:

1 + 1/2 + 1/3 + 1/4 + 1/5 + …

This diverges!
(I.e., it grows infinitely large, despite the fact that each number you add on is smaller than the previous one!
It's just that it's not small enough to make the summation converge.)

The final point about summations that I want to make is the notation for it.
The symbol for a summation is the capital Greek letter sigma,
which kind of looks like a backwards "3" with angles instead of curves:

Σ

Just as with the big union and big intersection symbols, we can use this as a shorthand;
so, instead of writing:

a1 + a2 + a3 + a4 + …

we'll write:

Σ an

But we have to say where n begins and where it "ends".
Typically, for an infinite summation, it won't end,
so we use the infinity sign, which looks like the numeral "8" lying on its side:

Below the Σ, we write something like "n=1" or "n=0" to indicate where we start adding,
depending on whether the range of the sequence is Z+ or N,
and above the Σ we write either "n=k", if we want to stop at the kth term, or "∞" if we want the infinite sum.
So the summation above could be written something like:

Σ an
n=1

or, if we write it like this:

ΣnZ+ (an)

it kind of looks like a quantifier expression with a bound variable.

It is essentially what programming languages call a "for-loop" or a "count-loop":
For n = 1 to infinity, or for n = 1 to k, add up the numbers or the output of the function (i.e., the numbers in the sequence).

Copyright © 2009 by William J. Rapaport (rapaport@buffalo.edu)
http://www.cse.buffalo.edu/~rapaport/191/F09/seqsum.html-20091106