$$ \newcommand{\norm}[1]{\left\Vert#1\right\Vert} \newcommand{\abs}[1]{\left\vert#1\right\vert} \newcommand{\set}[1]{\left\{#1\right\}} \newcommand{\Comp}{\mathbb C} \newcommand{\Real}{\mathbb R} \newcommand{\Nat}{\mathbb N} \newcommand{\of}[1]{\left ( #1 \right ) } \newcommand{\To}{\rightarrow} \newcommand{\eps}{\varepsilon} $$

Integral Calulus lecture notes: Sequences and sums

Eugene Kritchevski, Vanier College, Version January 2016

Material covered in these notes: What we do here will be useful in the near future for studying the area under the graph of a function (Riemann sums). We will also use the material developped in these notes for the last part of the course on infinite sequences and series.

To view some of the interactive features of this document you may need to install the CDF player and browser plugin on your computer: link to download and install.

The Odd Number Theorem and other odd ideas

If you add consecutive odd integers strating from $1$, you may discover something interesting. $$1=1=1^2$$ $$1+3=4=2^2$$ $$1+3+5=9=3^2$$ $$1+3+5+7=16=4^2$$ $$1+3+5+7+9=25=5^2$$ $$\vdots$$ The pattern discovered can be stated as a theorem.
The Odd Number Theorem
The sum of $n$ consecutive odd integers, starting from $1$, is given by $n^2$.
Suppose that your friend looked at sums of even numbers starting from $2$. $$2=2$$ $$2+4=6$$ $$2+4+6=12$$ $$2+4+6+8=20$$ $$2+4+6+8+10=30$$ $$\vdots$$ There might be a patten here as well (do you see it?) but let us say that the pattern is not completely obvious. Suppose that your friend discovered a pattern and stated it as a theorem.
The Even Number Theorem (claimed by your friend)
The sum of $n$ consecutive even integers, starting from $2$, is given by the formula $(*)$ below: $$\left(\left(\frac{1}{120} (5-n) (n-4) (n-3)+1\right) (n-2)+4\right) (n-1)+2.$$
For instance, if we replace $n$ with $3$ in the formula $(*)$, we get $12$, which indeed gives the sum of the first three even numbers: $2+4+6=12$. If we replace $n$ with $5$, then we get $30$ which indeed gives the sum of the first five even numbers: $2+4+6+8+10=30$. You can check that your friend's theorem gives the correct answer if $1\leq n\leq 5$. The formula $(*)$ must be very clever, yet something seems very wrong. The expression $(*)$ is complicated and bizarre, especially compared to the simple and beautiful formula for the sum of the first $n$ odd numbers. It is hard to believe that $(*)$ expresses a universal truth. If $n=6$, then $(*)$ gives $41$ but the the sum of the first $6$ odd numbers is $2+4+6+8+10+12=42$. So $(*)$ gives the wrong answer for $n=6$. Actually $(*)$ gives the wrong answer for all $n\geq 6$.
Your friend's theorem is wrong!
Nevertheless, we learned something useful. Now we may start having doubts about our own Odd Number Theorem. We have only veryfied it for $1\leq n\leq 5$. How do we know that our formula is also true for all $n\geq 6$? Let us look at a couple more values of $n$.
For $n=6$, we have $1+3+5+7+9+11=36=6^2$.
For $n=7$, we have $1+3+5+7+9+11+13=49=7^2$.
For $n=8$, we have $1+3+5+7+9+11+13+15=64=8^2$.
As we check more cases, we believe more and more that the Odd Number Theorem should be true for all $n$. Yet, our understanding is very limited. We have no guarantee that the Odd Number Theorem will not break down for some $n$, like our friend's theorem did. Another fundamental problem is that we do not understand (yet) WHY the Odd Number Theorem is working.

Sometimes, pictures give us great insight about mathematics. Interactive pictures can be even more valuable. Take a look at the following applet and move the $n$-slider.
Odd Number Theorem from the Wolfram Demonstrations Project by Jay Warendorff

The pictures do not prove the Odd Number Theorem but suggest a new way of looking it, eventually leading to a proof. The number $n^2$ represents the area of a square of dimension $n\times n$. If we cut cut a square of dimension $(n-1)\times (n-1)$ from a square of dimension $n\times n$, we get an L-shaped region whose area turns out to be the $n^{th}$ odd number. For example $4^2-3^2=7$ and $7$ is the $4^{th}$ odd number. This geometrical observation can be proved for all $n$ using simple algebra: $$n^2-(n-1)^2=n^2-(n^2-2n+1)=2n-1,$$ and $2n-1$ is precisely the $n^{th}$ odd number. Now the Odd Number Theorem can be proved by adding the $n$ equations below: $$\begin{align*} 1^2&=1\\ 2^2-1^2&=3\\ 3^2-2^2&=5\\ &\vdots\\ n^2-(n-1)^2&=2n-1. \end{align*}$$ On the left hand side, all the terms cancel except for $n^2$ and on the right hand side we get the sum of the first $n$ odd integers: $$n^2=1+3+5+\cdots+(2n-1).$$ This completes the proof of the Odd Number Theorem.

Exercise:
  1. Compute $1+3+5+...+1001$ without a calculator.
  2. Compute $123+125+127+...+1001$ without a calculator.
  3. The correct formula for summing the first $n$ even integers is $$2+4+\cdots+2n=n(n+1)$$
    4. Verify the formula for $n=1,2,3,4$ and $5$. Does this verification prove the formula?
We (re)discovered the Odd Number Theorem accidentally, by playing with sums of odd numbers. The geometrical illustration gave us a hint about the proof. This is very inspiring way of doing mathematics but in many problems the patterns are not obvious. For example, suppose we that we need to understand how to compute the sum the squares of consecutive integers: $$1^2=1$$ $$1^2+2^2=5$$ $$1^2+2^2+3^2=14$$ $$1^2+2^2+3^2+4^2=30$$ $$1^2+2^2+3^2+4^2+5^5=55$$ $$\vdots$$ There exists of course a pattern followed the numbers $1,5,14,30,55,\cdots$ as well as a beautiful geometrical illustration, but these are hard to guess. The next section will introduce the concept of a sequence of numbers and a versatile notation for dealing with sums. With these tools, one can prove observed patterns and also discover new formulas, when no pattern is clear.

Sequences and sums

A sequence is an infinite, ordered list of real numbers. For example, the odd numbers form the sequence $$\set{1,3,5,7,\cdots}$$ and reciprocals of positive integers form the sequence $$\set{\frac{1}{1},\frac{1}{2},\frac{1}{3},\frac{1}{4},\cdots}.$$ A sequence $$\set{a_1,a_2,a_3,a_4,\cdots}$$ is also denoted by $\set{a_n}_{n=1}^{\infty}$ or simply $\set{a_n}$. We refer to $a_n$ as the $n^{th}$ term of the sequence. Thus $a_1$ if the $1^{st}$ term, $a_2$ is the $2^{nd}$ term, $a_3$ is the $3^{rd}$ term, and so on.

With this notation, the sequence $\set{a_n}_{n=1}^{\infty}$ where $a_n=2n-1$ gives the odd numbers: $a_1=2\cdot1-1=1,a_2=2\cdot2-1=2,a_3=2\cdot3-1=5$, and so on. The sequence $\displaystyle\set{\frac{1}{n}}$ gives the reciprocals of positive integers: $\displaystyle\set{\frac{1}{1},\frac{1}{2},\frac{1}{3},\frac{1}{4},\cdots}.$

Exercise: Write out the first few terms for each of the sequences below.

(a)$\displaystyle\qquad\set{n(n+1)}_{n=1}^{\infty}$

(b) $\displaystyle\qquad\set{\frac{(-1)^{n-1}}{2^n}}_{n=1}^{\infty}$

Find a formula for the $n^{th}$ term for each of the sequences below.

(c)$\displaystyle\qquad\set{5,8,11,14,17,\cdots}$

(d)$\displaystyle\qquad\set{7,0.7,0.07,0.007,0.0007,0.00007,\cdots}$


Remarks about the notation
  1. The sequence $\set{a_n}_{n=1}^{\infty}$ can as well be denoted by $\set{a_i}_{i=1}^{\infty}$, $\set{a_k}_{k=1}^{\infty}$, $\set{a_m}_{m=1}^{\infty}$ or with any other letter playing the role of an index as long as confusing notations such as $\set{a_a}_{a=1}^{\infty}$ are avoided. For instance, $\set{2i-1}_{i=1}^{\infty}$ and $\set{2n-1}_{n=1}^{\infty}$ yield exactly the same sequence of odd integers.
  2. It is sometimes convenient to start sequences with index $0$ instead of $1$. The sequence $$\set{a_0,a_1,a_2,a_3,a_4,\cdots}$$ is then denoted by $\set{a_n}_{n=0}^{\infty}$.
  3. The concept of a sequence is very general and one can consider sequences of things other then numbers. For example, $\set{e^{nx}}_{n=1}^{\infty}$ is a sequence of exponential functions: $$\set{e^x,e^{2x},e^{3x},\cdots}.$$
Computations or proofs involving sums of many terms of a sequence can be greatly simplyfied using the sigma notation. For example, the expression $$a_4+a_5+a_6+\cdots+a_{100}$$ is compactly written in the sigma notation as $$\sum_{n=4}^{100}a_n.$$ The uppercase greek letter sigma $\sum$ is the summation sign. The variable $n$ is the index of summation. We are summing all the terms $a_n$ with $n$ ranging from the starting index $4$ up to the stopping index $100$. Note that $n$ is a dummy variable here and other letter coould be used for the index of summation. The same sum can be denoted by $$\sum_{i=4}^{100}a_i,\qquad \sum_{j=4}^{100}a_j,\qquad \sum_{k=4}^{100}a_k,$$ and so on.
More examples: $$3^2+5^2+6^6\cdots+100^2=\sum_{n=3}^{100}n^2=\sum_{i=3}^{100}i^2$$ $$1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots+\frac{1}{2048}=\sum_{k=0}^{11}\frac{1}{2^k}$$ $$1+3+5+7+9+\cdots+101=\sum_{i=1}^{51}(2i-1)$$ If we want to a have a variable stopping index, let us call it $n$, then we need to use a different letter for the index of summation. For instance $$a_1+a_2+\cdots+a_n=\sum_{i=1}^{n}a_i=\sum_{k=1}^{n}a_k.$$ The notation $\displaystyle\sum_{n=1}^{n}a_n$ is extremely confusing and should be avoided.
Exercise: Write the following sums using the sigma notation.
  1. $3^2+4^2+5^3+\cdots+10^2$
  2. $\frac{1}{1}+\frac{1}{2}+\cdots+\frac{1}{n}$
  3. $a_m+a_{m+1}+\cdots+a_{n-1}+a_n$
Basic algebraic properties of summation can be compactly expressed with the sigma notation.
The order of summation can be rearranged: the property $$(a_1+b_1)+(a_2+b_2)+\cdots+(a_n+b_n)=(a_1+a_2+\cdots+a_n)+(b_1+b_2+\cdots+b_n)$$ becomes, in sigma notation, $$\sum_{i=1}^{n}(a_i+b_i)=\sum_{i=1}^{n}a_i+\sum_{i=1}^{n}b_i.$$ Similarly, for differences: $$\sum_{i=1}^{n}(a_i-b_i)=\sum_{i=1}^{n}a_i-\sum_{i=1}^{n}b_i.$$

Factoring out a constant: if $c$ is a constant then $$(c a_1+c a_2+\cdots+c a_n)=c (a_1+a_2+\cdots+a_n)$$ which, in sigma notation, becomes $$\sum_{i=1}^{n}c a_i=c\sum_{i=1}^{n}a_i.$$
Computing sums in practice can be tricky. Let us take the lazy approach and see what kind of sums be computed with minimal effort. Summing constants is easy.
If $c$ is a constant, then $\displaystyle\sum_{i=1}^{n}c=\underbrace{c+c+c+\cdots+c}_{n \textrm{ terms}}= cn.$
It is also easy to compute sums when almost everything cancels out like in $$(b_1-b_0)+(b_2-b_1)+(b_3-b_2)+(b_4-b_3)+(b_5-b_4)+(b_6-b_5)+(b_7-b_6)+(b_8-b_{7})=b_8-b_0.$$ Such sums are called telescoping and in general we have:
Telescoping sum formula
We have $$(b_1-b_0)+(b_2-b_1)+(b_3-b_2)+\cdots+(b_n-b_{n-1})=b_n-b_0.$$ In sigma notation, the formula reads $$\sum_{i=1}^{n}(b_i-b_{i-1})=b_n-b_0.$$
The sigma notation is very powerful. For example, the identity $$i^2-(i-1)^2=i^2-(i^2-2i+1)=2i-1,$$ the basic summation properties and the telescoping sum formula with $b_i=i^2$ allow us to give a concise proof of the Odd Number Theorem: $$\sum_{i=1}^{n}(2i-1)=\sum_{i=1}^{n}i^2-(i-1)^2=n^2-0^2=n^2.$$ We can also discover the pattern for summing the first $n$ consecutive even numbers starting from $2$. We first write them as a sequence $$\set{2,4,8,10,\cdots}=\set{2i}_{i=1}^{\infty},$$ and then use the Odd Number Theorem: $$n^2=\sum_{i=1}^{n}(2i-1)=\sum_{i=1}^{n}2i -\sum_{i=1}^{n}1=-n+\sum_{i=1}^{n}2i.$$ Therefore:
$$\sum_{i=1}^{n}2i=n^2+n=n(n+1)$$
Divide by $2$ and get a formula for the sum of $n$ consecutive integers starting from $1$:
$$\begin{equation}\label{sumint} \sum_{i=1}^{n}i=\frac{1}{2}n^2+\frac{1}{2}n=\frac{1}{2}n(n+1) \end{equation}$$
For a geometrical illustration of \eqref{sumint}, take a look at either this applet or at this one.

Let us get creative. Instead of the telescoping sum for $b_i=i^2$, we take $b_i=i^3$. Then $$b_i-b_{i-1}=i^3-(i-1)^3=i^3-(i^3-3i^2+3i-1)=3i^2-3i+1,$$ and so $$\sum_{i=1}^{n}(3i^2-3i+1)=\sum_{i=1}^{n}i^3-(i-1)^3=n^3-0^2=n^3.$$ Now split the left of the above equation and solve for $\sum_{i=1}^{n}i^2$ using formula \eqref{sumint} $$\sum_{i=1}^{n}3i^2+\sum_{i=1}^{n}-3i+\sum_{i=1}^{n}1=n^3.$$ $$3\sum_{i=1}^{n}i^2-3\sum_{i=1}^{n}i+n=n^3$$ $$3\sum_{i=1}^{n}i^2-3\of{\frac{1}{2}n^2+\frac{1}{2}n}+n=n^3$$ $$3\sum_{i=1}^{n}i^2=n^3+\frac{3}{2}n^2+\frac{1}{2}n$$ $$\sum_{i=1}^{n}i^2=\frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n.$$ The last degree $3$ polynomial in $n$ can be factored as $\frac{1}{6}n(n+1)(2n+1)$. Thus we get, by calculation rather than pattern guessing, a formula for the sum of the squares of the first $n$ positve integers:
$$\begin{equation}\label{sumintsquare} \sum_{i=1}^{n}i^2=\frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n=\frac{1}{6}n(n+1)(2n+1) \end{equation}$$
For a geometrical illustration of \eqref{sumintsquare}, take a look here.
Exercise:
  1. Using the telescoping sum for $b_i=i^4$, together with formulas \eqref{sumint} and \eqref{sumintsquare}, show that $$\begin{equation}\label{sumintcube} \sum_{i=1}^{n}i^3=\frac{1}{4}n^4+\frac{1}{2}n^3+\frac{1}{4}n^2=\of{\frac{n(n+1)}{2}}^2. \end{equation}$$ Take a look here for beautiful geometrical illustration.
    2. $$\,$$
  2. Using the telescoping sum for $b_i=i^5$, find a formula for $\sum_{i=1}^{n}i^4$.
Note for the curious. For each integer power $p\geq 0$, there exists a formula for summing $\sum_{i=1}^{n}i^p$. Take a look at the following applet, which gives the formula for different values of $p$, in both expanded and factored form. Can you see any pattern? Hint: start by examining the highest powers of $n$ in the expanded form. For further investigation look up "Bernouilli numbers"...