Processing math: 100%

Discrete Mathematics Study Center

Home Course Notes Exercises Mock Exam About

Sequences and Sums

A sequence is a function from a subset of $\mathbb{Z}$ (usually $\{0,1,2,3,\ldots\}$ or $\{1,2,3,\ldots\}$) to a set $S$. We use $a_n$ to refer to the image of the integer $n$. We call $a_n$ a term of the sequence. The sequence itself is denoted $\{a_n\}$.

For example, if $a_n = 1/n$, then the sequence $\{a_n\}$ (beginning with $a_1$) is $a_1,a_2,a_3,\ldots$, or $1, 1/2, 1/3, 1/4, \ldots$.

A geometric sequence has the form $a, ar, ar^2, ar^3, \ldots, ar^n$ where $a$ is the initial term (a real number) and $r$ is the common ratio (also a real number). Typically, we think of such a sequence as starting with $n=0$ (since $ar^0 = a$). Here are some examples of geometric sequences:

• $\{b_n\}, b_n = (-1)^n$ has $a=-1,r=-1$ and looks like $-1,1,-1,1,-1,\ldots$
• $\{c_n\}, c_n = 2 \times 5^n$ has $a=10,r=5$ and looks like $10,50,250,1250,\ldots$
• $\{d_n\}, d_n = 6 \times \left(\frac{1}{3}\right)^n$ has $a=2, r=1/3$ and looks like $2, 2/3, 2/9, 2/27,\ldots$

An arithmetic sequence has the form $a, a+d, a+2d, a+3d, \ldots, a+nd$ where $a$ is the initial term and $d$ is the common difference. Typically, we think of such a sequence as starting with $n=0$ (since $a+0d = a$). Here are some examples of arithmetic sequences:

• $\{s_n\}, s_n = -1+4n$ has $a=-1,d=4$ and looks like $-1,3,7,11,\ldots$
• $\{t_n\}, t_n = 7-3n$ has $a=7,d=-3$ and looks like $7,4,1,-2,\ldots$

One common operation on sequences is to compute a sum of certain portions of the sequence. Suppose we have $a_1,a_2,a_3,\ldots,a_m,a_{m+1},a_{m+2},\ldots,a_n,\ldots$ and we want to consider the sum from $a_m$ to $a_n$: $a_m + a_{m+1} + a_{m+2} + \cdots + a_n$. We can write this using sigma notation: $$\sum_{i=m}^n a_i$$ where:

• $n$ is the upper limit
• $m$ is the lower limit
• $i$ is the index of summation

There is nothing special about using $i$; any (unused) variable would work!

Here are some examples of summations and sigma notation:

• The sum of the first $100$ terms of $\{a_n\}$ where $a_n = 1/n$ is $\displaystyle \sum_{i=1}^{100} a_i = \sum_{i=1}^{100} \frac{1}{i}$
• To compute the sum of the first $5$ squares, we have $$\begin{array}{rcl} \displaystyle \sum_{j=1}^5 j^2 &=& 1^2 + 2^2 + 3^2 + 4^2 + 5^2 \\ &=& 1 + 4 + 9 + 16 + 25 \\ &=& 55 \end{array}$$

Sometimes we might want to change the lower/upper limits without changing the sum. For example, suppose we want to change the sum $\displaystyle \sum_{j=1}^5 j^2$ to be written with lower limit $0$ and upper limit $4$. Then let $k=j-1$ to get $\displaystyle \sum_{j=1}^5 j^2 = \sum_{k=0}^4 (k+1)^2$

We can also split a sum up: $$\sum_{i=1}^n a_i = \sum_{i=1}^5 a_i + \sum_{i=6}^n a_i$$

This means that to exclude the first few terms of a sum, we can say: $$\sum_{i=6}^n a_i = \sum_{i=1}^n a_i - \sum_{i=1}^5 a_i$$

Summations can also be nested: $$\sum_{i=1}^n \sum_{j=1}^n ij$$

As an example, we compute $\sum_{i=1}^4 \sum_{j=1}^3 ij$: $$\begin{array}{rcl} \sum_{i=1}^4 \sum_{j=1}^3 ij &=& \sum_{i=1}^4 (1i + 2i + 3i) \\ &=& \sum_{i=1}^4 6i \\ &=& 6 + 12 + 18 + 24 \\ &=& 60 \end{array}$$

When every term is multiplied by the same thing, we can factor it out: $$\sum_{i=1}^n 6i = 6 \times \sum_{i=1}^n i$$

Here is another example of factoring, this time with a nested summation: $$\sum_{i=1}^4 \sum_{j=1}^3 ij = \sum_{i=1}^4 \left( i \times \sum_{j=1}^3 j \right) = \sum_{i=1}^4 6i = 6 \times \sum_{i=1}^4 i = 6 \times 10 = 60$$

You can also split over addition: $$\sum_{i=1}^n (i+2^i) = \sum_{i=1}^n i + \sum_{i=1}^n 2^i$$ This does not work for multiplication!

One useful tool is the sum of a geometric sequence, where $a,r \in \mathbb{R}$ and $r \neq 0$: $$\sum_{j=0}^n ar^j = \begin{cases} \frac{ar^{n+1}-a}{r-1} & \text{if } r \neq 1 \\ (n+1)a & \text{if } r = 1 \\ \end{cases}$$

Why does this work? Let $S = \sum_{j=0}^n ar^j$. Then: $$\begin{array}{rcl} rS &=& r \sum_{j=0}^n ar^j \\ &=& \sum_{j=0}^n ar^{j+1} \\ &=& \sum_{k=1}^{n+1} ar^k \\ &=& \sum_{k=0}^n ar^k + (ar^{n+1} - a) \\ &=& S + (ar^{n+1} - a) \end{array}$$

Therefore, $rS = S + (ar^{n+1} - 1)$, so $S = \frac{ar^{n+1}-a}{r-1}$ as long as $r \neq 1$ (the case when $r=1$ is easy).

Here are some more useful summation formulas:

• $\sum_{k=1}^n k = \frac{n(n+1)}{2}$
• $\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$
• $\sum_{k=1}^n k^3 = \frac{n^2(n+1)^2)}{4}$
• $\sum_{k=0}^\infty x^k = \frac{1}{1-x}$ when $|x| \lt 1$
• $\sum_{k=1}^\infty kx^{k-1} = \frac{1}{(1-x)^2}$ when $|x| \lt 1$

Try to derive some of these yourself. For example, $\sum_{k=1}^n k = \frac{n(n+1)}{2}$ can be derived by letting $S = \sum_{k=1}^n k$ and observing that: $$\begin{array}{ccccccccccccc} S & = & 1 & + & 2 & + & 3 & + & \cdots & + & k-1 & + & k \\ S & = & n & + & n-1 & + & n-2 & + & \cdots & + & 2 & + & 1 \\\hline 2S & = & (n+1) & + & (n+1) & + & (n+1) & + & \cdots & + & (n+1) & + & (n+1) \\ \end{array}$$

Since there are $n$ terms, we have $2S = n(n+1)$, so $S = \frac{n(n=1)}{2} = \sum_{k=1}^n k$.