# Sequences

A numerical sequence is a collection of numbers indexed by integers.

Sequences are usually indexed by the integers $$\ge 1$$, but sometimes the indexing can start from 0 or can include negative integers.

Examples of sequences and their first few terms are ($$n\ge1$$): \begin{align*} t_n &= 2n + 1:\quad 3,5,7,9, \dots\\ u_n &= 3^n: \qquad 3,9,27,81, \dots\\ v_n &= n!: \qquad 1,2,6,24,120,720, \dots \\ w_n &= (-1)^n: \quad 1,-1,1,-1,1, \dots \end{align*}

The general term (usually written as $$u_n$$) of the sequence is written as a function of the integer $$n$$.

For instance, the general term of the sequence $$3, 5,7, \dots$$ is $$u_n=2n+1$$.

Recall that $$x! = 1\times 2 \times \dots \times n-1 \times n.$$

Sequences can be described by whether they are bounded or not.

- A sequence is bounded if it it stays between two numbers (bounds).
- It is bounded from above if it stays below a given number (upper bound).
- It is bounded from below if it stays above a given number (lower bound).

$$u_n$$ is bounded from below by $$2$$ but not from above. $$v_n$$ and $$w_n $$ are bounded.

We can say that both $$v_n$$ and $$w_n$$ are bounded below by $$-2$$ and above by $$37$$, or we can say that they are bounded above by $$100$$. We can choose different numbers to use as the bounds, but we do not change the bounds as $$n$$ changes.

A recurrence relation is a sequence that expresses the general term using previous terms. The recurrence relation is generally specified by a function $$f$$, with $$$u_n=f(u_{n-1})$$$ for all $$n$$. To get all the terms, we need to specify the initial conditions involving at least the first term.

The relation $$u_n=u_{n-1}$$ for all $$n$$ means that all successive terms are equal ($$u_0=u_1=u_2=\dots$$), so the sequence is constant.

A recurrence relation may express $$u_n$$ in terms of more than one term. The number of initial conditions will change accordingly.

The Fibonacci sequence starts with $$F_0=0, F_1=1$$ and recursively $$$F_n=F_{n-1}+F_{n-2}.$$$ So $$F_2=F_1+F_0=1$$, $$F_3=F_2+F_1=2$$ and so on. The sequence is $$0$$, $$1$$, $$1$$, $$2$$, $$3$$, $$5$$, $$8$$, $$\cdots$$. We need to set both $$F_0$$ and $$F_1$$.

Proof by induction is the most common way of showing that a sequence has a given property. Properties that can be proved by induction are usually recursive.

As an example, we want to show the following property for all $$n\ge1$$, which we call $$P_n$$: $$$ S_n = 1+2+\dots + n =\frac{n(n+1)}{2} $$$

The method of induction contains two steps:

- Base case: Prove the statement for the first integer ($$n=1$$).
- Inductive step: Assume $$P_n$$ is true, and deduce $$P_{n+1}$$ from it.

$$P_1$$ is proved by the base case. From the established inductive step, we deduce that $$P_2$$ is true, then $$P_3$$ is true, and so on.

- In our example, the base case $$P_1$$ is true as $$S_1 = 1 = \frac{1\times 2}{2}$$
- For the inductive step, we assume $$P_n$$ ($$S_n = n(n+1)/2$$) and prove $$P_{n+1}$$: \begin{align*} S_{n+1} &= S_n + (n+1) = \frac{n(n+1)}{2} + (n+1) \\ &= \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2} \end{align*}

We conclude by induction that the property $$P_n$$ is true for all integers.

Sequences can be described by the way their values change.

- A sequence is increasing if $$u_n\le u_{n+1}$$ for all $$n$$.
- It is strictly increasing if $$u_n\lt u_{n+1}$$ for all $$n$$
- A sequence is decreasing if $$u_n\ge u_{n+1}$$ for all $$n$$.
- It is strictly decreasing if $$u_n\gt u_{n+1}$$ for all $$n$$.
- A sequence is monotonic if it is either increasing or decreasing, but not a combination of both.

In the US, increasing is sometimes used instead of strictly increasing ($$\lt$$) and non-decreasing for increasing ($$\le$$).

$$u_n=n+1/2 $$ is strictly increasing. $$v_n=6/n$$ is strictly decreasing. $$w_n=(-1)^n$$ is neither increasing nor decreasing overall.