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}

Advertisements

About Alex Nelson

I like math. I like programming. Most of all, I love puzzles.
This entry was posted in Series. Bookmark the permalink.

4 Responses to Finite Series

  1. Pingback: Riemann Summation | My Math Blog

  2. Pingback: Example Riemann Sums | My Math Blog

  3. Pingback: [Index] Calculus of a Single Variable | My Math Blog

  4. Pingback: [Index] Calculus in a Single Variable | My Math Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s