Sequences & Summations

Sequence

• 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 "α", and, instead of writing the outputs as α(0), α(1), α(2), etc., they are often written using subscripts:
  α0, α1, α2, ..., αn, αn+1, ...
• Here are a couple of examples:
  0, 1, 4, 9, 16, 25, ...
  This is a sequence where
  α₀ = 0
  α₁ = 1
  α₂ = 4
  α₃ = 9
  α₄ = 16
  α₅ = 25, etc.
• It can be described as follows:
  α_n = n², for all n
  0, 1, 1, 2, 3, 5, 8, 13, ...
• This is a sequence where
  α₀ = 0
  α₁ = 1
  α₂ = 1
  α₃ = 2
  α₄ = 3
  α₅ = 5
  α₆ = 8
  α₇ = 13, etc.
• It can be described as follows:
  α₀ = 0
  α₁ = 1
  α_n = α_n-1 + α_n-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 α_-1, α_-2, etc.
• You might want to try to figure out what those terms of the sequence would be.)
• In other words, there's nothing wrong with a sequence described as follows:
  α₀ = 0
  α₁ = 1
  α₂ = 2
  α₃ = 3
  α₄ = 4
  α₅ = 5
• Do you think a₆ = 6? It might. But I could continue as follows if I want to be perverse:
  α_n = 27ⁿ, for all n such that 5 < n < 123
  α_n = 3, for all n > 123
• I.e., the sequence is:
  0, 1, 2, 3, 4, 5, 27⁶, 27⁷, 27⁸, ..., 27¹²², 3, 3, ...
• That's a weird, uninteresting sequence, but it is a sequence.

Summations

• 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
  α₁, α₂, ..., α_n, ...,
  the corresponding summation is
  α₁ + α₂ + ... + α_n + ...
• 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 α_n = +1/(2n-1)
  else α_n = -1/(2n-1)
• Check it out:
  Odd(1), so α₁ = 1/(2*1 - 1) = 1/(2-1) = 1/1 = 1
  Even(2), so α₂ = -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:
α₁ + α₂ + α3 + α₄ + ...

• we'll write:
• Σ α_n

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:

or, if we write it like this:

• Σn∈Z⁺ (α_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).