Finite sequences of natural numbers



A sequence is an ordered list of terms.

These are commonly maps from natural numbers to real (or complex) numbers.

We can use \(a_i=f(i)\) to denote this.

If \(f(i)\) is defined on all \(i\in \mathbb{N}\) then the sequence is infinite. Otherwise it is finite.

If a sequence is defined on \(n\in \mathbb{N}\) and \(n\ne 0\) then the sequence must be defined on \(n-1\).

For example \(a_0, a_1, a_2,...\) is a sequence, but \(a_1,a_2,...\) is not.

Monotone sequence

A monotone sequence is one where each element is succeeded ordinally by the next entry.

For example:

\(<1,2,3,6,7>\) is monotone

\(<1,2,3,3,4>\) is not monotone

An increasing sequence is one where:

\(\forall m \in \mathbb{N} \forall n\in \mathbb{N} [m > n \leftrightarrow a_m \ge a_n]\)

A strictly increasing sequence is one where:

\(\forall m \in \mathbb{N} \forall n\in \mathbb{N} [m > n \leftrightarrow a_m > a_n]\)

A decreasing sequence is one where:

\(\forall m \in \mathbb{N} \forall n\in \mathbb{N} [m > n \leftrightarrow a_m \le a_n]\)

A strictly decreasing sequence is one where:

\(\forall m \in \mathbb{N} \forall n\in \mathbb{N} [m > n \leftrightarrow a_m < a_n]\)

All strictly decreasing sequences are decreasing, and all strictly increasing sequences are increasing.

A monotone sequence is one which is either increasing or decreasing.


A subsequence of a sequence is the original sequence with some elements of the original removed, not changing the order.

For example:

\(<1,3,5>\) is a subsequence of \(<2,1,3,4,7,5>\)



A series is the summation of a sequence. For a series \(a_n\) there is a corresponding series:




Multiplication of summations

If all members of a sequence are multiplied by a constant, so is each member of the series.

We can take constants out of the series:




Summation of constants

If all elements of a sequence are the same, then the series is a multiple of that constant.




Addition of summations

Consider a sequence \(a_i=b_i+c_i\).



We can then split this out.


Summation from a different start point


Multiple summations

\(\sum^n_{i=0} \sum^m_{j=0} a_i=n\sum^m_{j=0} a_i\)

\(\sum^n_{i=0} \sum^m_{j=0} a_i b_j=\sum^n_{i=0}a_i\sum^m_{j=0}b_i\)



A product is a repeated multiplication of a sequence.


Multiplication of products

We can take constants out of the product.



Products of constants

If \(a_i=c\) then the summation is then of the form:




Combining products

If a sequence is the product of to other sequences then the product of the sequence is equal to the product of the two individual sequences.





A factorial is a a product across natural numbers. That is:


Summation of natural numbers


Let’s prove that:

\(\sum_{i=0}^n i= \dfrac{n(n+1)}{2}\)

Proof by induction

We use the inference rules Modus Ponens, which says that if \(X\) is true, and \(X\rightarrow Y\) is true, then \(Y\) is true.

True for \(n=0\)

We know this is true for \(n=0\):



If it’s true for \(n\), it’s true for \(n+1\)

We can also prove that if it true for \(n\), it is true for \(n+1\).

\(\sum_{i=0}^{n+1} i= \dfrac{(n+1)(n+2)}{2}\)

\((n+1)+\sum_{i=0}^{n} i= \dfrac{n^2 +3n +2}{2}\)

If it is true for \(n\), then:

\((n+1)+\dfrac{n(n+1)}{2}= \dfrac{n^2 +3n +2}{2}\)

\(\dfrac{n^2+3n+2}{2}= \dfrac{n^2 +3n +2}{2}\)



So we know that it is true for \(n=0\), and if it is true for \(n\), then it is true for \(n+1\). As a result it is true for all natural numbers.

Bounded sequences

Bounded sequences

A function \(f(x)\) on set \(X\) is bounded if:

\(\exists M\in \mathbb{R} [\forall x\in X f(x)\le M]\)

A bounded sequence is a special case of a bounded function where:


That is, a sequence is bounded by \(M\) iff:

\(\forall n\in \mathbb{R} |f(a_n)|\le M\)