Just as the concept of a number is fundamental in mathematics, so is the concept of an ordered list of items. We extend the system of logic and natural numbers defined thus far by adding to it the concept of two basic kinds of ordered lists.
A finite sequence of length $n$ (also called an $n$-tuple) is a numbered list of items, one for each of the natural numbers less than $n$. A infinite sequence is numbered list of items, one for each of the natural numbers. In both cases, we will refer to the number assigned to a given item in the sequence as its standard index. Thus, the first item in a sequence will always have a standard index of 0.
The items in a sequence are called its terms. The the same item can appear more than once, i.e., terms with different standard indices can be equal. Two sequences are equal if and only if all of their corresponding terms (those with the same standard index) are equal. The length of a finite sequence is the same as the number of terms.
One consequence of this is that every sequence that has terms must have a term with index $0$ which must come before every other term in the sequence. This is called the first ($1^\text{st}$) term. Similarly if there is a term with index 1, we call it the second ($2^\text{nd}$) term, and so on with a term of index $k$ called the $(k+1)^\text{st}$ term of the sequence.
Thus, every sequence that has terms has a first term. Additionally, no term of an infinite sequence can be preceded in the list by infinitely many terms. Indeed, every term has an index $m$ and must have exactly $m$ terms that precede it (one for each natural number less than $m$).
Thus, an ordered list like the integers $\ldots,-3,-2,-1,0,1,2,3,\ldots$ is not considered to be a sequence, nor do is an ordered list such as $2,4,6,8,\ldots,1,3,5,7,\ldots$ where we first list all of the even positive natural numbers followed by all of the odd ones.
Finite sequences are frequently denoted by simply listing their terms in order from left to right separated by commas, with the whole thing optionally enclosed in brackets.
For example, $$\langle S,E,Q,U,E,N,C,E\rangle$$ is a sequence of length 8 whose first term is $S$, second term is $E$, and so on. These can be numbered in order from left to right with the natural numbers less than 8 as shown:
$$\langle\underset{0}{S},\underset{1}{E},\underset{2}{Q},\underset{3}{U},\underset{4}{E},\underset{5}{N},\underset{6}{C},\underset{7}{E}\rangle$$
Infinite sequences cannot be completely denoted in this manner, but are often informally (and somewhat ambiguously) written by writing their first few terms followed by an ellipsis. For example, we might write the infinite sequence of odd natural numbers as $$\langle 1,3,5,7,\ldots\rangle$$ This sequence can be numbered in order with the natural numbers as indicated $$\langle\underset{0}{1},\underset{1}{3},\underset{2}{5},\underset{3}{7},\ldots\rangle$$ Infinite sequences written in this manner are ambiguous because the reader must make assumptions about what terms are omitted, and so this notation is only used informally.
A similar informal notation can be used for finite sequences when there are too many terms to conveniently list them all, by using an ellipsis in place of missing terms. For example, we might denote the sequence of even integers less than 100 as $$\langle0,2,4,6,\ldots,96,98\rangle$$ which are indexed $$\langle\underset{0}{0},\underset{1}{2},\underset{2}{4},\underset{3}{6},\ldots,\underset{48}{96},\underset{49}{98}\rangle$$ Note that the ellipsis can represent as many terms as we like since the notation is informal. Since the sequence of length 0 has no terms, it can be denoted $\langle~\rangle$. The surrounding parentheses are frequently omitted when it is clear from the context that it is a sequence, for example, $$ \begin{align*} &S,E,Q,U,E,N,C,E \\ & \qquad\qquad \xor \\ &x _ 1,x _ 3,x _ 5,x _ 7,\ldots \\ & \qquad\qquad \xor \\ &0,2,4,\ldots,96,98 \end{align*} $$
Another way to represent a sequence is with a lamba expression $\lambda k.E$ where $k$ is either a natural number or a natural number less than some natural number $n$. If $a=(\lambda k.E)$ is such an expression it defines a sequence such that $a(k)$ is the term of the sequence with index $k$.
One big advantage to this representation is that it allows us to represent infinite sequences unambiguously. It is so useful that we define several special new expressions to represent such sequences.
Definition If $n$ is a natural number and $a=(\lambda k,E)$ we define $a _ k=a(k)$. We write $\langle a _ k\rangle _ {k=0}^\infty$ for the infinite sequence whose term with index $k$ is $a _ k$. Similarly, we write $\langle a _ k\rangle _ {k=0}^n$ for the finite sequence of length $n$ whose term with index $k$ is $a _ k$.
Comparing this notation to the listing notation we have $$\langle a _ k \rangle _ {k=0}^n=\langle a _ 0,a _ 1,a _ 2,\ldots,a _ n \rangle$$ and $$\langle a _ k \rangle _ {k=0}^\infty=\langle a _ 0,a _ 1,a _ 2,\ldots \rangle$$
In particular, we can express the sequence of all odd integers both rigorously and unambiguously as $$\langle 2k+1 \rangle _ {k=0}^\infty=\langle 1,3,5,7,\ldots \rangle$$ and the sequence of even numbers less than 100 as $$\langle 2k \rangle _ {k=0}^{49}=\langle 0,2,4,\ldots,96,98 \rangle$$
In everyday use, and in mathematics in particular, we often place items in order by numbering them with consecutive natural numbers that do not necessarily start with zero. For example it is frequently natural to index the first element of sequence with 1 instead of zero so that the $k^\text{th}$ term has index $k$.
Thus, while we always use a sequence of consecutive natural number for the indices of a sequence, it is sometimes convenient to reindex a sequence so that its first term has an index other than 0.
Definition Let $m,n$ be a natural numbers. Then $$\langle a _ k \rangle _ {k=m}^\infty=\langle a _ m,a _ {m+1},a _ {m+2},\ldots \rangle=\langle a _ {m+k} \rangle _ {k=0}^\infty$$ Furthermore, if $m+j=n$ then $$\langle a _ k \rangle _ {k=m}^n=\langle a _ m,a _ {m+1},\ldots,a _ n \rangle=\langle a _ {m+k} \rangle _ {k=0}^j$$ Finally if $n<m$ then $\langle a _ k \rangle _ {k=m}^n=\langle ~ \rangle$.
Sometimes a statement is not true for all naturals but rather is true for all sufficiently large natural numbers. In such a situation we can still prove such statements by induction if we reindex the statement we are trying to prove.
Prove the following form of induction is equivalent to the original form in which we stated induction. Let $a$ be a natural number and $P$ be some statement about natural numbers. Then $$\left( P(a) \xand \forall k. k\geq a \implies \left( P(k)\implies P(k+1) \right) \right) \implies \left( \forall n. n\geq a \implies P(n) \right)$$
Using this, we can expand this to a more useful rule of inference.
Induction (from $a$).
Let $a$ be any natural number.
Given
$\mc{P}(a)$ (base case)
Let $k$ be such that $a\leq k \xand \mc{P}(k)$
(inductive hypothesis)
$\mc{P}(\sigma(k))$
Conclude $\forall n.a\leq n \implies \mc{P}(n)$
One kind of definition that frequently goes hand-in-hand with such sequences and induction, are recursive definitions in which some sequence of entities is defined for some base case(s) first, and then new entities are defined in terms of previously defined objects of the same kind.
One convenient way to write such definitions is to use cases notation. \begin{equation}\label{eqn:cases} E = \begin{cases} \,v _ 1 & \text{if } P _ 1 \\ \,v _ 2 & \text{if } P _ 2 \\ \,\,\vdots & \,\vdots \\ \,v _ k & \text{otherwise} \end{cases} \tag{*} \end{equation} where $E$ is the expression being defined, $v _ 1,\ldots,v _ k$ are the values of the expression, and $P _ 1,\ldots,P _ k$ are mutually exclusive statements (i.e., exactly one of the statements is true) which specify the conditions for which $E$ has the given values. The final condition ‘otherwise’ is optional and is an abbreviation for $P _ k=\neg (P _ 1 \xor P _ 2 \xor \cdots \xor P _ {k-1})$. The entire equation given in (\ref{eqn:cases}) is an abbreviation for the statement $$(P _ 1\implies E=v _ 1)\xand (P _ 2\implies E=v _ 2) \cdots (P _ k\implies E=v _ k)$$
Similarly, we can define sequences recursively by lambda expressions, $a$ for which $a _ n$ is defined in terms of one or more values of $a _ k$ for $k<n$.
Here are a few common definitions related to recursively defined sequences. In the following table, $a$ is a lambda expression which produces terms which can be any type, and $k,m,n$ are natural numbers.
| Name | Definition |
|---|---|
| Subscript notation: | $a _ n=a(n)$ |
| Finite Sequence: | $\langle a _ k\rangle _ {k=0}^n=\langle a _ 0,a _ 1,\ldots,a _ n\rangle$ |
| Reindexed Finite Sequence | $\langle a _ k\rangle _ {k=m}^{n+m} = \langle a _ {k+m}\rangle _ {k=0}^{n}$ |
| Infinite Sequence: | $\langle a _ k\rangle _ {k=0}^\infty=\langle a _ 0,a _ 1,a _ 2,\ldots\rangle$ |
| Reindexed Infinite Sequence: | $\langle a _ k\rangle _ {k=m}^\infty=\langle a _ {k+m}\rangle _ {k=0}^\infty$ |
| Summation: | $\displaystyle\sum _ {k=0}^0 a _ k =a _ 0 \qu \xand \qu \sum _ {k=0}^{\sigma(n)} a _ k = \,a _ {\sigma(n)} + \sum _ {k=0}^n a _ k $ |
| Reindexed Summation: | $\displaystyle\sum _ {k=m}^m a _ k =a _ m \qu \xand \qu \sum _ {k=m}^{n+1+m} a _ k = \,a _ {n+1+m} + \sum _ {k=m}^{n+m} a _ k $ |
| Powers: | $z^0 = 1 \qu\xand\qu z^{\sigma(n)}=z\cdot z^n$ |
| Factorial: | $0! = 1 \qu\xand\qu \sigma(n)!=\sigma(n)\cdot n!$ |
| Fibonacci Numbers: | $F _ 0=1,\qu F _ 1=1\qu\xand\qu F _ {n+2} = \,F _ {n+1}+F _ n$ |
| Multinomial coefficients | $\hbinom{n}{0}=\hbinom{0}{m}=1\qu\xand\qu \hbinom{n+1\>}{m+1}=\hbinom{n+1\>}{m}+\hbinom{n\>}{m+1}$ |
| Binomial coefficients: | $\binom{n+m}{n}=\hbinom{n}{m}$ |
Remarks:
Sequences and Recursion
Declare Sum, F, !, multinomial, choose and ^ to be constants.
Summation. $\displaystyle\sum_{k=0}^{0} \mc{P}\left(k\right)=\mc{P}\left(0\right)$ and $\displaystyle\sum_{k=0}^{\sigma\left(n\right)} \mc{P}\left(k\right)=\mc{P}\left(\sigma\left(n\right)\right)+\displaystyle\sum_{k=0}^{n} \mc{P}\left(k\right)$
Natural Number Exponentiation. $z^0=1$ and $z^\sigma(n)=z\cdot z^n$
Factorial. $0!=1$ and $\sigma(n)!=\sigma(n)\cdot n!$
Fibonacci Numbers. $F_0=1$, $F_1=1$, and $F_{n+2}=F_{n+1}+F_n$
Multinomial coefficients. $(m,0)=1$, $(0,n)=1$, and $\left(\sigma\left(m\right),\sigma\left(n\right)\right)=\left(\sigma\left(m\right),n\right)+\left(m,\sigma\left(n\right)\right)$
Binomial coefficients. $\binom{n+m}{m}=\left(n,m\right)$
From now on, we will allow ‘by arithmetic’ as a shortcut for justifying facts about natural number constants that could be checked on an ordinary calculator. Thus, we can justify facts like $2+3=5$ or $5<13$ with the reason ‘by arithmetic’ and no premises. This shortcut only applies to statements involving numerical constants, not variables or expressions involving variables. The statement can only contain natural number constants (e.g. $0$, $1$, $2$, etc) the operators $+$, $\cdot$, and $\text{^}$, and the relations $=$, $\neq$, $\leq$, and $\lt$. We do not allow subtraction or division since the natural numbers aren’t closed under those operations.
Prove the following theorems.
The natural number $k!$ is always positive.
Power laws If $m,n,w,z$ are natural numbers then
useful basics If $a,b,n$ are natural numbers and $a\neq 0$ then
If $a,b$ are natural numbers then for all $n\geq a+b$, $$a\cdot n+b < n^2$$
Basic sum properties Suppose \(n\) and $s$ are natural numbers, and $(a)\ _ {k=0}^n$ and $\left(b\right)\ _ {k=0}^n$ are finite sequences of natural numbers. Then
For all natural numbers $n\geq 5$, $$n^2<2^n$$
Let $n$ be a natural number. Then $$F _ {n+3}+F _ n=2\cdot F _ {n+2}$$
Symmetry of binomial coefficients For any natural numbers $n$ and $m$, $$\binom{n+m}{n}=\binom{n+m}{m}$$.
Sum of the first $n$ odd numbers The sum of the first $n$ odd numbers is $n^2$, i.e., $$\sum _ {k=0}^n (2k+1) = (n+1)^2$$
For all natural numbers $n\geq 4$, $$2^n<n!$$
Gauss’s Formula For every natural number $n$, $$2\cdot \sum _ {k=0}^n k = n\cdot(n+1)$$
Closed formula for binomial coefficients For all natural numbers $n$ and $m$, $$n!\cdot m!\cdot\binom{n+m}{n}=(n+m)!$$
Transposing summations Given natural numbers $m,n$, and sequences $(a)\ _ {k=0}^m$ and $(b)\ _ {j=0}^n$, $$\sum _ {k=0}^m\sum _ {j=0}^n a _ k b _ j = \sum _ {j=0}^n\sum _ {k=0}^m a _ k b _ j$$
For all natural numbers $n$, $$F _ {2(n+1)} = F _ {n+1}\cdot(F _ {n+2} + F _ n )$$
Let $n$ be a natural number. Then $$\sum _ {k=0}^n F _ k = F _ {n+2}$$
Row sum in Pascal’s triangle Given a natural number $n$, $$\sum _ {k=0}^n \binom{n}{k} = 2^n$$
Define $a$ to be the infinite sequence satisfying $$a _ 0=1 \xand a _ {n+1}=a _ n+8n$$ for all natural numbers $n$. Then for all $n\neq 0$, $$a _ {n+1}=(2n+1)^2$$
Suppose $n$ is a natural number. Then $$\sum _ {k=0}^n \binom{n}{k}\cdot F _ k = F _ {2n}$$
For all natural numbers $n$, $$F _ n<2^n$$
If $n$ is a natural number and $k\leq n$, then $$(k+1)\cdot\binom{n+1}{k+1}=(n+1)\cdot\binom{n}{k}$$
For any natural number $n$, $$1+\sum _ {k=0}^n k\cdot k! = (n+1)!$$
For any natural number $n$, $$\sum _ {k=0}^{n+1} k^2\cdot (k+1)! = n\cdot (n+3)!+2$$
hockey stick identity For all natural numbers $n$, $$\sum _ {k=m}^{n}\binom{k}{m}=\binom{n+1}{m+1}$$
Define a recursive sequence $a$ such that $a _ 0=0$ and for all natural numbers $n$ we have $a _ {n+1}=3\cdot a _ n+2$ Then $$2\cdot a _ n+1=3^n$$
AM-GM Inequality For all natural numbers $m$ and $n$ $$4\cdot m\cdot n \leq (m+n)^2$$
binomial theorem For any natural numbers $x$ and $n$, $$(1+x)^n=\sum _ {k=0}^n\binom{n}{k}\cdot x^k$$
