## Finite Series

1. Sigma Notation. A sequence is an ordered set. We will deal with finite sequences. We write
(1)$\displaystyle \{a_{k}\}.$
Now, we can form a series by
(2)$\displaystyle \sum_{k=1}^{n}a_{k}=a_{1}+a_{2}+a_{3}+\dots+a_{n}$
Some terminology:
(3)$\displaystyle \sum^{\langle\text{last index}\rangle}_{k=\langle\text{first index}\rangle}a_{k}$
We call the “${\sum}$” the sigma notation (it’s a capital sigma, ${\Sigma}$, for “sum”) and we call the small subscript ${k}$ in ${a_{k}}$ an index. So what are some examples?

Example 1 Consider ${\{a_{k}=k^{-3}\text{ for }k=1,2,3,4,5\}}$. What is its sum? It is
(4)$\displaystyle \begin{array}{rl} \displaystyle\sum^{5}_{k=1}a_{k} &= \displaystyle\sum^{5}_{k=1}k^{-3}\\ &= \displaystyle\frac{1}{1}+\frac{1}{2^{3}}+\frac{1}{3^{3}}+\frac{1}{4^{3}}+\frac{1}{5^{3}} \end{array}$
Note the difference between powers, e.g. ${2^{3}=8}$, and subscripts (e.g. ${a_{k}}$).

Example 2 Another series
(5)$\displaystyle \sum^{4}_{k=1}\frac{k}{1+k^{2}}=\frac{1}{1+1}+\frac{2}{1+2^{2}}+\frac{3}{1+3^{2}}+\frac{4}{1+4^{2}}$
which has 4 terms.

Example 3 A simpler example
(6)$\displaystyle \sum^{3}_{i=2}i=2+3$
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
(7)$\displaystyle \sum^{n}_{j=1}a_{j}=\sum^{n}_{k=1}a_{k}$
without any problem.

Finite sums are called “Finite Series”.

There are some rules for simplifying sums:

Sum Rule: suppose we have two sequences ${a_{k}}$, ${b_{k}}$. The sum ${\displaystyle\sum^{n}_{k=1}(a_{k}+b_{k})}$ can be rearranged as
(8)$\displaystyle \sum^{n}_{k=1}(a_{k}+b_{k})=\left(\sum^{n}_{k=1}a_{k}\right)+\left(\sum^{n}_{k=1}b_{k}\right).$
Difference Rule: ${\displaystyle \sum^{n}_{k=1}(a_{k}-b_{k})=\left(\sum^{n}_{k=1}a_{k}\right)-\left(\sum^{n}_{k=1}b_{k}\right)}$

Constant Multiple Rule: Let ${c}$ be a constant, then
(9)$\displaystyle \sum^{n}_{k=1}ca_{k} = c\sum^{n}_{k=1}a_{k}$
Constant Sum Rule: Let ${A}$, ${B}$ be constants, then
(10)$\displaystyle \sum^{n}_{k=1}(Aa_{k}+Bb_{k})=A\left(\sum^{n}_{k=1}a_{k}\right)+B\left(\sum^{n}_{k=1}b_{k}\right).$

Note that the constant sum rule implies the others. For example, when ${A=B=1}$, we get the sum rule; when ${A=c}$ and ${B=0}$ we get the constant multiple rule; and when ${A=1}$ and ${B=-1}$ we get the difference rule.

2. Gauss’ Sum. Let ${n}$ be any positive integer. Then
(11)$\displaystyle \sum^{n}_{k=1}k=\frac{n(n+1)}{2}$
How can we prove this?

Suppose ${n=2m}$ were even. Then writing out the sum:
(12)$\displaystyle \sum^{2m}_{k=1}k = 1 + 2 + \dots + 2m$
We can rearrange the terms writing
(13)$\displaystyle 1 + 2 + \dots + 2m = 1 + 2m + 2 + (2m-1) + 3 + (2m-2) + \dots$
So we can group these into pairs:
(14)$\displaystyle 1 + 2m + 2 + (2m-1) + \dots = \bigl[1 + 2m\bigr] + \bigl[2 + (2m-1)\bigr] + \dots + [m + (m+1)]$
How many such pairs exist? There are ${m=n/2}$ such pairs, each summing to ${2m+1=n+1}$. Thus for even ${n}$, the sum is
(15)$\displaystyle \sum^{2m}_{k=1}k = \frac{2m(2m+1)}{2}=\frac{n(n+1)}{2}.$
What about odd ${n}$?

Write ${n=2m+1}$. Then we have
(16)$\displaystyle \sum^{n}_{k=1}k = \left(\sum^{2m}_{k=1}k\right)+\left(\sum^{2m+1}_{k=2m+1}k\right).$
Using our previous result, we can rewrite the right hand side as
(17)$\displaystyle \left(\sum^{2m}_{k=1}k\right)+\left(\sum^{2m+1}_{k=2m+1}k\right) =\left(\frac{2m(2m+1)}{2}\right)+2m+1$
Observe by simple arithmetic we have
(18)$\displaystyle \begin{array}{rl} \displaystyle\left(\frac{2m(2m+1)}{2}\right)+2m+1 &=\displaystyle\frac{4m^{2}+2m+4m+2}{2}\\ &=\displaystyle\frac{(2m+1)(2m+2)}{2}\\ &=\displaystyle\frac{n(n+1)}{2} \end{array}$
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 $n$. We pick $n=1$. The sum is trivial

$\displaystyle\sum^{1}_{k=1}k=1$

Inductive Hypothesis: we suppose that Gauss’ formula works for any $n$:
$\displaystyle\sum^{n}_{k=1}k=\frac{n(n+1)}{2}$
But we’re not done yet! We need to prove that when $n$ changes to $n+1$ 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:
$\displaystyle\sum^{n+1}_{k=1}k=\left(\sum^{n+1}_{k=1}k\right)+(n+1)$
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
$\displaystyle\left(\sum^{n+1}_{k=1}k\right)+(n+1)=\left(\frac{n(n+1)}{2}\right)+(n+1)$
Using basic arithmetic, we simplify this to be
$\displaystyle\left(\frac{n(n+1)}{2}\right)+(n+1)=\frac{n(n+1)+2(n+1)}{2} = \frac{(n+2)(n+1)}{2}$
This is precisely Gauss’ formula for $n+1$.

This concludes the inductive proof for Gauss’ formula.

Exercise 1. Prove by induction $\displaystyle \sum^{n}_{k=1}k^{2}=\frac{1}{6}n(n+1)(2n+1)$

Exercise 2. Prove by induction $\displaystyle \sum^{n}_{k=1}k^{3}=\left(\frac{n(n+1)}{2}\right)^{2}$