Finite sequences of natural numbers

Sequences

Definition

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.

Subsequences

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>$$

Series

Definition

A series is the summation of a sequence. For a series $$a_n$$ there is a corresponding series:

$$s_n=\sum_{i=0}^na_n$$

Where:

$$\sum_{i=0}^na_i=a_0+a_1+a_2+...+a_n$$

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:

$$s_n=\sum_{i=0}^na_i$$

$$s_n=\sum_{i=0}^ncb_i$$

$$s_n=a\sum_{i=0}^nb_i$$

Summation of constants

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

$$s_n=\sum_{i=0}^na_i$$

$$s_n=\sum_{i=0}^nc$$

$$s_n=nc$$

Consider a sequence $$a_i=b_i+c_i$$.

$$s_n=\sum_{i=0}^na_i$$

$$s_n=\sum_{i=0}^n(b_i+c_i)$$

We can then split this out.

$$s_n=\sum_{i=0}^nb_i+\sum_{i=0}^nc_i$$

Summation from a different start point

$$\sum_{i=0}^na_i=a_0+\sum_{i=1}^na_i$$

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$$

Products

Definition

A product is a repeated multiplication of a sequence.

$$p_n=\prod_{i=0}^ns_i$$

Multiplication of products

We can take constants out of the product.

$$p_n=\prod_{i=0}^nca_i$$

$$p_n=a^{n}\sum_{i=0}^na_i$$

Products of constants

If $$a_i=c$$ then the summation is then of the form:

$$p_n=\prod_{i=0}^nc$$

$$p_n=c^{n}\prod_{i=j}^n1$$

$$p_n=c^{n}$$

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.

$$p_n=\prod_{i=0}^na_i$$

$$p_n=\prod_{i=0}^nb_ic_i$$

$$p_n=\prod_{i=0}^nb_i\prod_{i=0}^nc_i$$

Factorials

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

$$n!:=\prod^n_{i=0}i$$

Summation of natural numbers

Goal

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$$:

$$0=\dfrac{0(0+1)}{2}$$

$$0=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}$$

$$1=1$$

Result

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:

$$X=\mathbb{N}$$

That is, a sequence is bounded by $$M$$ iff:

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