# Discrete Mathematics: An Active Approach to Mathematical Reasoning

## Section5.1Sequences

In this section we look at the mathematical concept of sequences. Although many sequences themselves are straightfoward, such as $$2, 4, 6, 8, \ldots\text{,}$$ we need to introduce notation and terminology for working with general sequences.

### Definition5.1.1.

A sequence is an ordered list.
We use the notation $$a_1, a_2, a_3, \ldots, a_k, \ldots$$ for a general sequence.
Each $$a_k$$ is called a term in the sequence. The subscript $$k$$ is called the index. The index will be an integer, and almost always a nonnegative integer. The first term $$a_1$$ (or sometimes $$a_0$$) is called the initial term. The term $$a_k$$ is called the $$k^{th}$$ term. It is also often called the general term of the sequence.
Consider the sequence $$2, 4, 6, 8, 10, \ldots\text{.}$$ The initial term is $$a_1=2\text{.}$$ The $$k^{th}$$ term is $$a_k=2k\text{.}$$
We need to be careful with subscripts. For example, $$a_{4+1}=a_{5}=10\text{,}$$ but $$a_{4}+1=8+1=9\text{.}$$ If we add 1 to the index, we get the next term, which is not the same as adding 1 to the term.
We can define a sequence by giving the general term.
Let $$a_k=2^k, k\geq 0\text{.}$$ Give the first five terms of the sequence.
1, 2, 4, 8, 16
Let $$a_k=2^k, k\geq 0\text{.}$$ Give the $$k+1$$ term of the sequence.
$$a_{k+1}=2^{k+1}$$
Let $$a_k=\frac{1}{k+1}, k\geq 1\text{.}$$ Give the first five terms of the sequence.
1/2, 1/3, 1/4, 1/5, 1/6
Let $$a_k=\frac{1}{k+1}, k\geq 1\text{.}$$ Give the $$k+1$$ term of the sequence.
$$a_{k+1}=\frac{1}{k+2}$$

### Activity5.1.1.

Consider the sequence $$a_k=(-1)^k$$ for $$k\geq 0\text{.}$$

#### (a)

Write the first 5 terms of the sequence.

#### (b)

What is the initial term?

### Activity5.1.2.

Consider the sequence $$a_k=\frac{1}{k-1}$$ for $$k\geq 3\text{.}$$

#### (a)

Write the first 5 terms of the sequence.

#### (b)

What is the initial term?

### Activity5.1.3.

Consider the sequence $$0, 1, -2, 3, -4, 5, \ldots\text{.}$$ Find a general formula for the $$k$$th term, $$a_k\text{.}$$
We are going to look at many examples where we want to add terms in a sequence. The following notation will be helpful when working with sums.

### Summation Notation.

We can write a sum using sigma or summation notation:
\begin{equation*} a_1+a_2+\cdots +a_n=\sum_{k=1}^{n}a_k. \end{equation*}
We read $$\sum_{k=1}^{n}a_k$$ as “the sum of $$a_k$$ from $$k=1$$ to $$n\text{.}$$
Find $$\sum_{k=1}^4 k\text{.}$$
$$1+2+3+4=10$$
Find $$\sum_{k=1}^5 k^2\text{.}$$
$$1^2+2^2+3^2+4^2+5^2=55$$
Find $$\sum_{k=1}^n k^2\text{.}$$
$$1^2+2^2+3^2+\cdots+n^2$$
Find $$\sum_{k=2}^2 k^2\text{.}$$
$$2^2=4$$
Note, we can write the sum of only the $$m^{th}$$ term, $$\sum_{k=m}^{m}a_k=a_m\text{.}$$

### Activity5.1.4.

Consider the sum $$\sum_{k=1}^{5}(2k-1)\text{.}$$ Write out the summation and find the sum.

### Activity5.1.5.

Consider the sum $$\sum_{k=1}^{n}\frac{1}{k}\text{.}$$

#### (a)

Write out the summation.

#### (b)

Write out the summation for $$\sum_{k=1}^{n+1}\frac{1}{k}\text{.}$$ How do (a) and (b) differ?

#### (c)

Write out the summation for $$\sum_{k=0}^{n}\frac{1}{k+1}\text{.}$$ Is this the same as either of the previous sums?

### Activity5.1.6.

Consider the sum $$\sum_{k=1}^{n}\frac{1}{k(k+1)}\text{.}$$

#### (a)

Write out the summation.

#### (b)

Write out the summation for $$\sum_{k=1}^{n+1}\frac{1}{k(k+1)}\text{.}$$ How do (a) and (b) differ?
Just as we can add several terms of a sequence, the following notation alllows us to multiply several terms of a sequence using product notation:
\begin{equation*} a_1\cdot a_2\cdot a_3\cdots a_n=\prod_{k=1}^{n}a_k. \end{equation*}
Find $$\prod_{k=1}^4 k\text{.}$$
$$1\cdot2\cdot3\cdot 4=24$$
Find $$\prod_{k=1}^3 k^2\text{.}$$
$$1^2\cdot2^2\cdot3^2=36$$

### Activity5.1.7.

Write out the following products.

#### (a)

$$\prod_{k=1}^{5}(2k-1)$$

#### (b)

$$\prod_{k=1}^{n+1}(2k)$$
Recall, we defined $$n$$ factorial in Definition 4.3.7: $$n!=(n)(n-1)\cdots(2)(1)\text{.}$$ We also need to define $$0!=1\text{.}$$
The following properties are helpful when working with sums and products.

### Properties of Sums and Products.

1. $$\displaystyle \sum_{k=m}^{n}a_k+\sum_{k=m}^{n}b_k=\sum_{k=m}^{n}(a_k+b_k)$$
2. $$\displaystyle c\sum_{k=m}^{n}a_k=\sum_{k=m}^{n}(ca_k)$$
3. $$\displaystyle \biggl(\prod_{k=m}^{n}a_k\biggr)\biggl(\prod_{k=m}^{n}b_k\biggr)=\prod_{k=m}^{n}(a_k\cdot b_k)$$

### Activity5.1.8.

Prove $$\sum_{k=1}^{n}a_k + \sum_{k=1}^{n}b_k=\sum_{k=1}^{n}(a_k+b_k)\text{.}$$
Hint.
Try writing out the sum rather than using summation notation.

### Definition5.1.6.

The number of subsets of size $$r$$ that can be chosen from a set of $$n$$ elements is $$n$$ choose $$r\text{.}$$ Notation $$\binom{n}{r}$$, read “$$n$$ choose $$r\text{.}$$
We can calculate the number of sets of $$r$$ objects chosen from $$n$$ objects with the following formula:
\begin{equation*} \binom{n}{r}=\frac{n!}{r!(n-r)!}. \end{equation*}
Calculate $$\binom{5}{3}\text{.}$$
$$\frac{5!}{3!2!}=10$$
Calculate $$\binom{5}{1}\text{.}$$
$$\frac{5!}{1!4!}=5$$
Calculate $$\binom{5}{4}\text{.}$$
$$\frac{5!}{4!1!}=5$$
Calculate $$\binom{5}{0}\text{.}$$
$$\frac{5!}{0!5!}=1$$

### Activity5.1.9.

Find $${6 \choose 3}$$ and $${6 \choose 0}\text{.}$$
When we get to mathematical induction in the next section, it will be important that we can work with summations when we want to add “the $$n+1$$ term” to a summation. In particular, the following observation is useful:
\begin{equation*} \biggl(\sum_{k=1}^{n}a_{k}\biggr)+a_{n+1}=\sum_{k=1}^{n+1}a_k. \end{equation*}
We should also note that there are often multiple ways to write the same sum.
Consider the sum $$1^2+2^2+3^2\text{.}$$ Depending on how we index the sum, we can write it in different ways.
If we index from $$k=1$$ to 3, we have $$\sum_{k=1}^3k^2=1^2+2^2+3^2\text{.}$$
If we index from $$k=2$$ to 4, we have $$\sum_{k=2}^4(k-1)^2=1^2+2^2+3^2\text{.}$$

#### 1.

Write the terms of $$\frac{k+1}{k+3}, 0\leq k\leq 4\text{.}$$

#### 2.

Write the terms of $$\frac{(-1)^k}{2k}, 1\leq k\leq 6\text{.}$$

#### 3.

Write the terms of $$\frac{(-1)^kk}{2}, 1\leq k\leq 4\text{.}$$

#### 4.

Write out the summation notation as a sum of terms: $$\sum_{k=1}^4 2k-1$$

#### 5.

Write out the summation notation as a sum of terms: $$\sum_{k=1}^n k^3$$

#### 6.

Write out the summation notation as a sum of terms: $$\sum_{k=1}^{n+1} k^3$$

#### 7.

Write out the summation notation as a sum of terms: $$\sum_{k=1}^4 \frac{(-1)^k}{k}$$

#### 8.

Write out the summation notation as a sum of terms: $$\sum_{k=1}^n \frac{(-1)^k}{k}$$

#### 9.

Write out the summation notation as a sum of terms: $$\sum_{k=1}^{n+1} \frac{(-1)^k}{k}$$

### ExercisesExercises

#### 1.

Find an explicit formula for the following sequences with the given initial terms.
1. $$\displaystyle \frac{1}{3}, \frac{4}{9},\frac{9}{27}, \frac{16}{81},\frac{25}{243}, \frac{36}{729}$$
2. $$\displaystyle 3, 6, 12, 24, 48, 96$$

#### 2.

Compute the given product or sum.
1. $$\displaystyle \prod_{k=2}^{4}{k^2}$$
2. $$\displaystyle \prod_{k=2}^{2}{\Bigl(1-\frac{1}{k}\Bigr)}$$
3. $$\displaystyle \sum_{k=-1}^{1}{(k^2+3)}$$

#### 3.

Write out the sum in expanded form.
1. $$\displaystyle \sum_{j=1}^{n}{j(j+1)}$$
2. $$\displaystyle \sum_{i=1}^{k+1}{i(i!)}$$

#### 4.

Rewrite by separating off the final term: $$\sum_{i=1}^{k+1}{i(i!)}$$

#### 5.

Write using product notation:
\begin{equation*} (2^2-1)\cdot(3^2-1)\cdot(4^2-1). \end{equation*}

#### 6.

Write using summation notation:
\begin{equation*} 1^3+2^3+3^3+\cdots+n^3. \end{equation*}

#### 7.

Transform the sum by making the change of variable $$j=i-1\text{:}$$
\begin{equation*} \sum_{i=1}^{n+1}\frac{(i-1)^2}{i\cdot n}. \end{equation*}

#### 8.

Simplify.
1. $$\displaystyle \frac{((n+1)!)^2}{(n!)^2}$$
2. $$\displaystyle \frac{n!}{(n-k+1)!}$$

#### 9.

Compute.
1. $$\displaystyle {3 \choose 0}$$
2. $$\displaystyle {n \choose n-1}$$
3. $$\displaystyle {n+1 \choose n-1}$$