Last Update: 25 March 2009
Note: or material is highlighted |
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:
Here are a couple of examples:
This is a sequence where
It can be described as follows:
This is a sequence where
It can be described as follows:
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 a_{1}, not a_{0};
it can also be continued backwards to
a_{–1}, a_{–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:
Do you think a_{6} = 6? It might. But I could continue as follows if I want to be perverse:
I.e., the sequence is:
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:
the corresponding summation is
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:
where:
Check it out:
Even(2), so a_{2} = –1/(2*2 – 1) = –1/(4–1) = –1/3
etc.
Now consider its summation:
= 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):
(Consider what happens when you multiply each term in the summation by 4:
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:
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:
we'll write:
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:
∞
Σ a_{n}
n=1
or, if we write it like this:
Σn∈Z^{+} (a_{n})
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).