Use adaptive quiz-based learning to study this topic faster and more effectively.

# Sequences

## Definitions and examples of 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.$

The sequence of triangular numbers has general term $n(n+1)/2$

## Monotonicity and boundedness of sequences

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.

Examples of sequences: $u_n$ and $v_n$ are bounded from below; $w_n$ is bounded (above and below).

## Recurrence relation

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

The first few values of the Fibonacci sequence

## Proof by induction

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.

## Increasing and decreasing sequences

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.

Examples of sequences: $u_n$ is increasing; $v_n$ is decreasing; $w_n$ is not monotonic.