# Sequences

Definition. A succession of real numbers $$a_1,a_2,\cdots,a_n,\cdots$$ in a definite order is called a sequence. $a_n$ is called the $n$-th term or the general term. The sequence $\{a_1,a_2,\dots,a_n,\cdots\}$ is denoted by $\{a_n\}$ or $\{a_n\}_{n=1}^\infty$.

Example.

1. The set of natural numbers $1,2,3,4,\cdots,n,\cdots$
2. $1,-2,3,-4,\cdots,(-1)^{n-1}n,\cdots$
3. $\frac{1}{2},-\frac{1}{4},\frac{1}{8},-\frac{1}{16},\cdots,(-1)^{n-1}\frac{1}{2^n},\cdots$
4. $0,1,0,1,\cdots,\frac{1}{2}[1+(-1)^n],\cdots$
5. $2,3,5,7,11,\cdots,p_n,\cdots$

It is not essential that the general term of a sequence is given by some simple formula as is the case in the first four examples above. The sequence in 5 represents the succession of prime numbers. $p_n$ stands for the $n$-th prime number. There is no formula available for the determination of $p_n$.

The following is the quantifying definition of the limit of a sequence due to Augustin-Louis Cauchy.

Definition. A sequence $\{a_n\}$ has a limit $L$ and we write $\lim_{n\to\infty}a_n=L$ or $a_n\to L$ as $n\to\infty$ if for any $\epsilon>0$ there exists a positive integer $N$ such that $$|a_n-L|<\epsilon\ \mbox{for all}\ n\geq N.$$

Example.

1. Show that $\lim_{n\to\infty}\frac{1}{n}=0$
2. Show that $\lim_{n\to\infty}\frac{1}{10^n}=0$
3. Let $\{a_n\}$ be a sequence defined by $$a_1=0.3, a_2=0.33, a_3=0.333,\cdots,$$ show that $\lim_{n\to\infty}a_n=\frac{1}{3}$

Proof. I will prove 1. 2 and 3 are left as exercises. Let $\epsilon>o$ be given. Then $|a_n-L|=\frac{1}{n}<\epsilon\Longrightarrow n>\frac{1}{\epsilon}$. Choose $N$ a positive integer $\frac{1}{\epsilon}$. Then for all $n>N$ $|a_n-L|<\epsilon$.

The following limit laws allow us to break a complicated limit to simpler ones.

Theorem. Let $\lim_{n\to\infty}a_n=L$ and $\lim_{n\to\infty}b_n=M$. Then

1. $\lim_{n\to\infty}(a_n\pm b_m)=L\pm M$
2. $\lim_{n\to\infty}ca_n=cL$ where $c$ is a constant.
3. $\lim_{n\to\infty}a_nb_n=LM$
4. $\lim_{n\to\infty}\frac{a_n}{b_n}=\frac{L}{M}$ provided $M\ne 0$.

Example. Find $\lim_{n\to\infty}\frac{n}{n+1}$.

Solution. \begin{align*}\lim_{n\to\infty}\frac{n}{n+1}&=\lim_{n\to\infty}\frac{1}{1+\frac{1}{n}}=1\end{align*} since $\lim_{n\to\infty}\frac{1}{n}=0$.

The following theorem is also an important tool for calculating limits of certain sequences.

Theorem (Squeeze Theorem). If $a_n\leq b_n\leq c_n$ for $n\geq n_0$ and $\lim_{n\to\infty}a_n=\lim_{n\to\infty}c_n=L$ then $\lim_{n\to\infty}b_n=L$.

Corollary. If $\lim_{n\to\infty}|a_n|=0$ then $\lim_{n\to\infty}a_n=0$.

Proof. It follows from the inequality $-|a_n|\leq a_n\leq |a_n|$ for all $n$ and the Squeeze Theorem.

Example. Use the Squeeze Theorem to show $$\lim_{n\to\infty}\frac{n!}{n^n}=0$$

Solution. It follows from $$0\leq\frac{n!}{n^n}=\frac{1\cdot 2\cdot 3\cdots n}{n\cdot n\cdot n\cdots n}\leq\frac{1}{n}$$ for all $n$.

The following theorem enables you to use a cool formula you learned in Calculus I, L’Hôpital’s rule!

Theorem. If $\lim_{x\to\infty}f(x)=L$ and $f(n)=a_n$, then $\lim_{n\to\infty}a_n=L$.

Example. Calculate $\lim_{n\to\infty}\frac{\ln n}{n}$.

Solution. Let $f(x)=\frac{\ln x}{x}$. Then $\lim_{x\to\infty}f(x)$ is an indeterminate form of  type $\frac{\infty}{\infty}$. So by L’Hôpital’s rule \begin{align*}\lim_{x\to\infty}\frac{\ln x}{x}&=\lim_{x\to\infty}\frac{(\ln x)’}{x’}\\&=\lim_{x\to\infty}\frac{1}{x}\\&=0\end{align*} Hence by the Theorem above $\lim_{n\to\infty}\frac{\ln n}{n}=0$.

Example. Calculate $\lim_{n\to\infty}\root n\of{n}$.

Solution. Let $f(x)=x^{\frac{1}{x}}$. Then $\lim_{x\to\infty}f(x)$ is an indeterminate form of type $\infty^0$. As you learned in Calculus I, you will have to convert the limit into an indeterminate form of type $\frac{\infty}{\infty}$ or type $\frac{0}{0}$ so that you can apply L’Hôpital’s rule to evaluate the limit. Let $y=x^{\frac{1}{x}}$. Then $\ln y=\frac{\ln x}{x}$. As we calculated in the previous example, $\lim_{x\to\infty}\ln y=0$. Since $\ln y$ is continuous on $(0,\infty)$, $$\lim_{x\to\infty}\ln y=\ln(\lim_{x\to\infty} y)$$ Hence, $$\lim_{x\to\infty}x^{\frac{1}{x}}=e^0=1$$ i.e. $\lim_{n\to\infty}\root n\of{n}=1$.

Theorem. $\lim_{n\to\infty}\root n\of{a}=1$ for $a>0$.

Example. $\lim_{n\to\infty}\frac{1}{\root n\of{2}}=1$.

Definition. A sequence $\{a_n\}$ is said to diverge if it fails to converge. Divergent sequences include sequences that tend to infinity or negative infinity, for example $1,2,3,\cdots,n,\cdots$ and sequences that oscillates such as  $1,-1,1,-1,\cdots$.

Definition. A sequence $\{a_n\}$ is said to be bounded if there exists $M>0$ such that $|a_n|<M$ for every $n$.

Theorem. A convergent sequence is bounded but the converse need not be true.

Definition. A sequence $\{a_n\}$ is said to be monotone if it satisfies either $$a_n\leq a_{n+1}\ \mbox{for all}\ n$$ or $$a_n\geq a_{n+1}\ \mbox{for all}\ n$$

Equivalently, one can show that a sequence $\{a_n\}$ is monotone increasing by checking to see if it satisfies  $$\frac{a_{n+1}}{a_n}\geq 1\ \mbox{for all}\ n$$ or $$a_{n+1}-a_n\geq 0\ \mbox{for all}\ n$$

The following theorem is called the Monotone Sequence Theorem.

Theorem. A monotone sequence which is bounded is convergent.

Example.

1. Show that the sequence $$\frac{1}{2},\frac{1}{3}+\frac{1}{4},\frac{1}{4}+\frac{1}{5}+\frac{1}{6},\cdots,\frac{1}{n+1}+\frac{1}{n+2}+\cdots+\frac{1}{2n},\cdots$$ is convergent.
2. Show that the sequence $$1,1+\frac{1}{2},1+\frac{1}{2}+\frac{1}{4},\cdots,1+\frac{1}{2}+\frac{1}{4}+\cdots+\frac{1}{2^n},\cdots$$ is convergent.

Solution. 2 is left as an exercise. $a_{n+1}-a_n=\frac{1}{2n+2}+\frac{1}{2n+1}-\frac{1}{n+1}=\frac{4n+1}{(2n+2)(2n+1)}>0$ for all $n$. So it is monotone increasing. $$a_n=\frac{1}{n+1}+\cdots+\frac{1}{n+n}\leq\frac{1}{n}+\cdots+\frac{1}{n}=\frac{n}{n}=1$$ for all $n$. So it is bounded. Therefore, it is convergent by the monotone sequence theorem.