1. Sigma Notation. A sequence is an ordered set. We will deal with finite sequences. We write
Now, we can form a series by
We call the “” the sigma notation (it’s a capital sigma, , for “sum”) and we call the small subscript in an index. So what are some examples?
Example 1 Consider . What is its sum? It is
Note the difference between powers, e.g. , and subscripts (e.g. ).
Example 2 Another series
which has 4 terms.
Example 3 A simpler example
This is a toy example we will expand upon later.
Now, note we can rewrite the same sum several different ways.
We can change the index
without any problem.
Finite sums are called “Finite Series”.
There are some rules for simplifying sums:
Sum Rule: suppose we have two sequences , . The sum can be rearranged as
Constant Multiple Rule: Let be a constant, then
Constant Sum Rule: Let , be constants, then
Note that the constant sum rule implies the others. For example, when , we get the sum rule; when and we get the constant multiple rule; and when and we get the difference rule.
2. Gauss’ Sum. Let be any positive integer. Then
How can we prove this?
Suppose were even. Then writing out the sum:
We can rearrange the terms writing
So we can group these into pairs:
How many such pairs exist? There are such pairs, each summing to . Thus for even , the sum is
What about odd ?
Write . Then we have
Using our previous result, we can rewrite the right hand side as
Observe by simple arithmetic we have
Thus we have proven Gauss’ formula.
3. Another Proof of Gauss’ Sum. We can use a technique called Mathematical Induction which is a three-step procedure.
Base Case: we prove Gauss sum works for some nice value of . We pick . The sum is trivial
Inductive Hypothesis: we suppose that Gauss’ formula works for any :
But we’re not done yet! We need to prove that when changes to Gauss’ formula still works. This is the next step…
Inductive Case: we write the formula out and try to connect it back to the inductive hypothesis:
We see that we have some constant plus a series which resembles the inductive hypothesis. We use the inductive hypothesis to rewrite our series as
Using basic arithmetic, we simplify this to be
This is precisely Gauss’ formula for .
This concludes the inductive proof for Gauss’ formula.
Exercise 1. Prove by induction
Exercise 2. Prove by induction