## Vocabulary and key concepts

### Vocabulary

#### Term

Suppose \(\displaystyle{\{a_1,a_2,a_3,\ldots\}}\) is a sequence of numbers. If \(\displaystyle{n}\) is a natural number then the number appearing in the \(\displaystyle{n}\) th spot of the sequence is referred to as the \(\displaystyle{n}\) th term of the sequence.

Consider the sequence of positive even numbers:

\(\displaystyle{\{2,4,6,8,\ldots\}}\)

Then we have the following:

- The fourth term of the first sequence is \(\displaystyle{8}\).
- The third term of the first sequence is \(\displaystyle{6}\).
- If \(\displaystyle{n}\) is a natural number then the \(\displaystyle{n}\) th term of the sequence is \(\displaystyle{2n}\).

### Recursive and explicit sequences

#### Recurrence equation

A recurrence equation is an equation that recursively defines a sequence of numbers.

Consider the following recurrence equation:

\(\displaystyle{a_{n+1}=a_n+a_{n-1}+3}\)

If \(\displaystyle{\{a_1,a_2,\cdots\}}\) is a sequence of numbers such that \(\displaystyle{a_{10}=9}\) and \(\displaystyle{a_{11}=10}\), then we have the following:

- \(\displaystyle{a_{12}=a_{11}+a_{10}+3=10+9+3=22}\)
- \(\displaystyle{a_{13}=a_{12}+a_{11}+3=22+10+3=35}\)

#### Recursive sequence

A recursive sequence \(\displaystyle{\{a_1,a_2,a_3,\ldots\}}\) is a sequence of numbers generated by a recurrence equation and a finite number of terms.

Let \(\displaystyle{\{a_1,a_2,a_3,\ldots\}}\) be the sequence with the following properties:

- \(\displaystyle{a_0=3}\)
- For any natural \(\displaystyle{n\geq1}\), \(\displaystyle{a_n=a_{n-1}+5}\)

Then the sequence is a recursive sequence and the recursive equation is \(\displaystyle{a_n=a_{n-1}+5}\).

The following list is the first few terms of this sequence:

\(\displaystyle{3,8,13,18,23,\ldots}\)

Some recursive sequences are determined by more than one term and a recursive equation.

Let \(\displaystyle{\{a_1,a_2,a_3,\ldots\}}\) be the sequence with the following properties:

- \(\displaystyle{a_1=1}\)
- \(\displaystyle{a_2=1}\)
- For all \(\displaystyle{n\geq 3}\) let \(\displaystyle{a_n=a_{n-1}+a_{n-2}}\)

Then the sequence is a recursive sequence and the recurrence equation is \(\displaystyle{a_n=a_{n-1}+a_{n-2}}\).

The following list is the first few terms of this sequence:

\(\displaystyle{1,1,2,3,5,8,13,21,34,55,89,\ldots}\)

Observe that each term is the sum of the previous two terms.

Given the beginning of a sequence of numbers \(\displaystyle{\{a_1,a_2,a_3,\ldots\}}\) it is useful to identify a pattern in order to study higher terms of the sequence. This can be accomplished by identifying a recurrence equation.

Consider the following sequence:

\(\displaystyle{\{1,-1,-5,-13,-29,\ldots\}}\)

The difference between the first two terms is:

\(\displaystyle{-1-1=-2}\)

The difference between the third term and second term is:

\(\displaystyle{-5-\left(-1\right)=-4}\)

The difference between the fourth term and third term is:

\(\displaystyle{-13 -\left(-5\right)=-8}\)

The difference between the fifth term and the fourth term is:

\(\displaystyle{-29-\left(-13\right)=-16}\)

Therefore the sequence satisfies the following recurrence equation:

\(\displaystyle{a_n-a_{n-1}=-2\left(n-1\right)}\)

The above recurrence equation is also equivalent to:

\(\displaystyle{a_n=a_{n-1}-2\left(n-1\right)}\)

If you are given the first few terms of a sequence, then one can only take an educated guess at the pattern of the sequence.

Consider the following sequence of numbers:

\(\displaystyle{\{2,2,0,-2,\ldots\}}\)

There are four terms of the sequence given so we can try and guess the explicit pattern to the sequence. However, nothing is for certain unless we are given an explicit recurrence equation.

The above sequence could be defined by a number of different recurrence equations. For example, it is possible that the above sequence is defined by one of the following:

- \(\displaystyle{a_1=a_2=2}\) and \(\displaystyle{a_n=a_{n-1}-a_{n-2}}\) for all \(\displaystyle{n\geq 3}\)
- \(\displaystyle{a_1=2}\) and \(\displaystyle{a_n= a_{n-1}-2^{n-2}}\) for all \(\displaystyle{n\geq 2}\)

#### Explicit sequence

An explicit sequence is a sequence of numbers \(\displaystyle{\{a_1,a_2,a_3,\ldots\}}\) such that for each natural number \(\displaystyle{n}\) the \(\displaystyle{n}\) -term of the sequence is defined by an explicit formula which only depends on \(\displaystyle{n}\).

A sequence can sometimes be explicit and recursive.

Consider the sequence of odd numbers \(\displaystyle{\{1,3,5,7,9,\ldots\}}\).

The sequence is recursive because for each \(\displaystyle{n}\) :

\(\displaystyle{a_{n+1}=a_{n}+2}\)

However, the sequence is also explicit because the \(\displaystyle{n}\) th term of the sequence is given by the following explicit formula:

\(\displaystyle{a_n=2\left(n-1\right)+1}\)

## Arithmetic and geometric sequences

### Arithmetic sequences

An arithmetic sequence is a sequence of numbers such that the difference between any two consecutive terms agree.

#### Arithmetic sequence

A sequence of numbers \(\displaystyle{\{a_1,a_2,a_3,\ldots\}}\) is an arithmetic sequence if there is a constant \(\displaystyle{c}\) such that for each \(\displaystyle{n}\) :

\(\displaystyle{a_{n+1}=a_n+c}\)

Consider the recursive sequence numbers defined by \(\displaystyle{a_1=7}\) and \(\displaystyle{a_n=a_{n-1}+4}\) for all \(\displaystyle{n\geq 2}\).

\(\displaystyle{\{7,11,15,19,23,\ldots\}}\)

The sequence is an arithmetic sequence since the difference of any two consecutive terms is \(\displaystyle{4}\).

A sequence \(\displaystyle{\{a_n\}}\) is demonstrated to be arithmetic by showing that there exists a constant \(\displaystyle{c}\) so that for each \(\displaystyle{n}\) :

\(\displaystyle{a_{n}-a_{n-1}=c}\)

Let's consider an arithmetic sequence of numbers \(\displaystyle{\{a_0,a_1,a_2,a_3,\ldots\}}\) such that for each \(\displaystyle{n}\) :

\(\displaystyle{a_{n+1}=a_n+c}\)

The sequence can also be written explicitly. For any natural *n*:

** \(\displaystyle{a_n=a_0+n.c}\) **

### Geometric sequences

A geometric sequence is a sequence of numbers such that the ratio of any two consecutive numbers agree.

#### Geometric sequence

A sequence of numbers \(\displaystyle{\{a_1,a_2,a_3,\ldots\}}\) is said to be geometric if there is a constant \(\displaystyle{c}\) such that for each \(\displaystyle{n}\) :

\(\displaystyle{a_{n+1}=ca_n}\)

Consider the sequence of numbers defined by \(\displaystyle{a_1=1}\) and \(\displaystyle{a_n=2a_{n-1}}\) for all \(\displaystyle{n\geq 2}\). The sequence is geometric because for each \(\displaystyle{n}\) :

\(\displaystyle{a_{n+1}=2a_n}\)

The first terms of the sequence are:

\(\displaystyle{1,2,4,8,16,32,\ldots}\)

Consider the following sequence of numbers defined by \(\displaystyle{a_1=6}\) and \(\displaystyle{a_n=\dfrac{1}{2}a_{n-1}}\) for all \(\displaystyle{n\geq 2}\). The sequence is a geometric sequence because for each \(\displaystyle{n}\) we have:

\(\displaystyle{a_{n+1}=\dfrac{1}{2}a_n}\)

The first terms of the sequence are:

\(\displaystyle{6, 3, \dfrac{3}{2}, \dfrac{3}{4},\ldots}\)

A sequence \(\displaystyle{\{a_n\}}\) is shown to be geometric by showing that there is a constant \(\displaystyle{c}\) such that for any natural number *n*:

** \(\displaystyle{\dfrac{a_{n+1}}{a_{n}}=c}\) **

Let's consider the geometric sequence of numbers \(\displaystyle{\{a_0,a_1,a_2,a_3,\ldots\}}\) such that for each \(\displaystyle{n}\) :

\(\displaystyle{a_{n+1}=a_n.c}\)

The sequence can also be written explicitly. For any natural *n*:

** \(\displaystyle{a_n=a_0.c^n}\) **

## Mathematical induction

### Principle

Mathematical induction is a method of proving mathematical statements indexed by natural numbers.

Before going through the process of how mathematical induction works, let's first explain its governing principle through an example.

Let's suppose we study genealogy and we wish to show that every member of a family posses gene \(\displaystyle{X}\). To do this we can trace back a family's heritage and show that a distant relative carried gene \(\displaystyle{X}\). We then prove that this family member passed gene \(\displaystyle{X}\) to their children and they passed gene \(\displaystyle{X}\) to their children and so on. In conclusion, we have inductively shown that every member of a family posses the gene \(\displaystyle{X}\).

#### Principal of mathematical induction

For every natural number \(\displaystyle{n}\) let \(\displaystyle{P\left(n\right)}\) be a mathematical statement. Suppose the following:

- The mathematical statement \(\displaystyle{P\left(1\right)}\) is true.
- For every natural number \(\displaystyle{k}\) the assumption that \(\displaystyle{P\left(k\right)}\) is true implies that \(\displaystyle{P\left(k+1\right)}\) is also true.

Then the mathematical statement \(\displaystyle{P\left(n\right)}\) is true for every natural number \(\displaystyle{n}\).

The principal of mathematical induction can be used to prove the following statement for every natural number \(\displaystyle{n\geq 1}\) :

\(\displaystyle{P\left(n\right)}\) "The number \(\displaystyle{11^n-1}\) is divisible by \(\displaystyle{10}\)."

Proof for \(\displaystyle{n=1}\)

The statement \(\displaystyle{P\left(1\right)}\) is:

" \(\displaystyle{11^1-1=10}\) is divisible by \(\displaystyle{10}\) "

It is indeed a true statement.

Proof of recurring pattern

To complete the proof, let's consider a natural number *k*. We assume the statement \(\displaystyle{P\left(k\right)}\) is true and show that \(\displaystyle{P\left(k+1\right)}\) is true.

Therefore we assume \(\displaystyle{11^k-1}\) is divisible by \(\displaystyle{10}\) and prove \(\displaystyle{11^{k+1}-1}\) is divisible by \(\displaystyle{10}\). Therefore we are assuming that there exists an integer \(\displaystyle{N}\) such that \(\displaystyle{11^k-1=10 N}\).

Therefore:

\(\displaystyle{11^{k+1}-1=11\cdot 11^{k}-1\\=11\cdot\left(10 N+1\right)-1\\=11\cdot 10 N+11-1\\=11\cdot 10 N +10\\=10\left(11 N+1\right)}\)

Therefore \(\displaystyle{11^{k+1}-1}\) is also divisible \(\displaystyle{10}\). \(\displaystyle{P\left(k+1\right)}\) is true.

Conclusion

By mathematical induction \(\displaystyle{11^n-1}\) is divisible by \(\displaystyle{10}\) for every natural number \(\displaystyle{n\geq 1}\).

### Use of mathematical induction

Mathematical induction can be used to prove the following formula:

\(\displaystyle{1+2+\cdots +n=\dfrac{n\left(n+1\right)}{2}}\)

In the setup of mathematical induction, the mathematical statement \(\displaystyle{P\left(n\right)}\) is:

" \(\displaystyle{1+2+\cdots +n=\dfrac{n\left(n+1\right)}{2}}\) "

Proof for \(\displaystyle{n=1}\)

Begin by checking the validity of \(\displaystyle{P\left(1\right):}\)

\(\displaystyle{\dfrac{1\left(1+1\right)}{2}=1}\)

Therefore \(\displaystyle{P\left(1\right)}\) is a true statement.

Proof of recurring pattern

Let *k* be a natural number. We assume the mathematical statement \(\displaystyle{P\left(k\right)}\) and try to show the validity of the mathematical statement \(\displaystyle{P\left(k+1\right)}\).

Consider the sum of the first \(\displaystyle{k+1}\) natural numbers:

\(\displaystyle{1+2+\cdots +k+k+1}\)

We are assuming \(\displaystyle{P\left(k\right)}\) is valid, that is:

\(\displaystyle{1+2+\cdots +k=\dfrac{k\left(k+1\right)}{2}}\)

Therefore we have the following:

\(\displaystyle{1+2+\cdots +k+k+1=\left(1+2+\cdots +k\right)+\left(k+1\right)\\=\dfrac{k\left(k+1\right)}{2}+k+1\\=\dfrac{k\left(k+1\right)}{2}+\dfrac{2k+2}{2}\\=\dfrac{k^2+3k+2}{2}\\=\dfrac{\left(k+1\right)\left(k+2\right)}{2}}\)

\(\displaystyle{P\left(k+1\right)}\) is true. We have shown the mathematical statement \(\displaystyle{P\left(k+1\right)}\) is implied by the mathematical statement \(\displaystyle{P\left(k\right)}\).

Conclusion

Therefore by mathematical induction:

\(\displaystyle{1+2+\cdots +n=\dfrac{n\left(n+1\right)}{2}}\)

for every natural number \(\displaystyle{n\geq 1}\).

Mathematical induction can be used to prove the sum of the first \(\displaystyle{n}\) odd numbers is \(\displaystyle{n^2}\). That is for each natural number \(\displaystyle{n\geq 1}\) :

\(\displaystyle{1+3+5+\cdots +\left(2n-1\right)=n^2}\)

In the setup of mathematical induction, the mathematical statement \(\displaystyle{P\left(n\right)}\) is:

" \(\displaystyle{1+3+5+\cdots +\left(2n-1\right)=n^2}\) "

Proof for \(\displaystyle{n=1}\)

Begin by checking validity of the mathematical statement \(\displaystyle{P\left(1\right)}\) :

\(\displaystyle{1=1^2}\)

Therefore the mathematical statement \(\displaystyle{P\left(1\right)}\) is valid.

Proof of recurring pattern

Let *k* be a natural number.

We assume that the mathematical statement \(\displaystyle{P\left(k\right)}\) is valid and try to derive the mathematical statement \(\displaystyle{P\left(k+1\right)}\). Therefore we assume the following:

\(\displaystyle{1+3+5+\cdots + \left(2k-1\right)=k^2}\)

and we try to prove the following:

\(\displaystyle{1+3+5+\cdots +\left(2\left(k+1\right)-1\right)=\left(k+1\right)^2}\)

This is done as follows:

\(\displaystyle{1+3+5+\cdots +\left(2\left(k+1\right)-1\right)\\=1+2+3+\cdots +\left(2k-1\right)+\left(2\left(k+1\right)-1\right)\\=k^2+2k+1\\=\left(k+1\right)^2}\)

\(\displaystyle{P\left(k+1\right)}\) is true.

Conclusion

Therefore by mathematical induction the sum of the first \(\displaystyle{n}\) odd numbers is \(\displaystyle{n^2}\).