Asymptotic Estimates

We will gradually develop an understanding on asymptotic estimates over the course. For now, we will deal with the most basic definitions. Let $\{a_n\}$ be a sequence of real numbers. We write $\lim_{n \rightarrow \infty} a_n = c$ (or $a_n \rightarrow c$) if

$(\forall \epsilon >0) (\exists n_0 \in {\mathbb N}) (\forall n \ge n_0) (|a_n - c| \leq \epsilon)$

Such a sequence is said to converge (when it has such a finite limit $c$), otherwise it is said to diverge (when such a finite limit does not exist).

We say that $\{a_n\}$ is bounded if $(\exists C, n_0)(\forall n \ge n_0)|a_n| \leq C$. One can naturally define the notion of sequences that are bounded from above and bounded from below. From this, it follows that every convergent sequence is bounded.

Example 19

Find a divergent sequence $\{a_n\}$ for which $\{(a_n)^2\}$ is convergent.

Proof:

We can define $a_n = (-1)^n$, which alternates between $-1$ and $1$, while $a_n^2$ is all ones.

Notice that, in the above example, $\{a_n\}$ is bounded, so boundedness does not necessarily imply convergence (while convergence implies boundedness). However, with an additional property, one can guarantee convergence.

Theorem 20

If $\{a_n\}$ is non-decreasing and bounded from above, then $\{a_n\}$ converges.

Exercise 50

Suppose $a_n \rightarrow K$ and $b_n \rightarrow L$. Show that

• $a_n + b_n \rightarrow K+L$
• $a_n \cdot b_n \rightarrow K \cdot L$
• If $L \neq 0$, $a_n/b_n \rightarrow K/L$
• If $a_n \geq 0$, then $\sqrt{a_n} \rightarrow \sqrt{K}$

An important relation about limits (that we would state here without proof) is the following:

Proposition 1

$\lim_{n \rightarrow \infty} (1+1/n)^n = e$

Notice that one can also see this as a definition. The sequence $a_n = (1+1/n)^n$ is strictly increasing and bounded, so from Theorem 20, the limit exists, and we call it $e$.

Example 20

Define the sequence $\{a_n\}$ by $a_0 = 1$ and $a_{n+1} = (\sqrt{2})^{a_n}$. Prove that $a_n$ converges.

Proof:

We will show that $a_n$ is increasing and bounded from above by $2$. First, we show that $\{a_n\}$ is less than $2$ by induction. The base case when $n=0$ is true. Now assume that it is true for all $n \leq n_0$ and consider $a_{n_0+1} = 2^{a_{n_0}/2}$. Since $a_{n_0} < 2$ by induction hypothesis, we have that $a_{n_0+1} < 2^{2/2} = 2$. To show that $a_n$ is increasing, we first need the fact that $2^x > x^2$ for all $x \in [1,2)$ (well, just plot the curve and it will be clear 😊). Next, we have $a_{n+1}^2 = 2^{a_n} > a_n^2$ (since $a_n \in [1,2)$¹). This implies that $a_{n+1} > a_n$ for all $n$.

With some more effort, one can show that the sequence in the above example converges to $2$. This is left as an exercise.

Exercise 51

Prove that the above sequence converges to two.

We say that $a_n$ is asymptotically equal to $b_n$ if $\lim_{n \rightarrow \infty} a_n/b_n =1$. When two sequences are asymptotically equal, it means that the two numbers are practically the same for every purpose, as long as $n$ is sufficiently large. This is denoted by $a_n \sim b_n$.

Exercise 52

Prove:

• $3n +10 \sim 3n$
• $n^2 - 10n +1 \sim n^2$

Exercise 53

Let $X$ be the set of sequences that have only positive values. Prove that $\sim$ defines an equivalence relation on $X$, i.e., prove that:

• $a_n \sim a_n$ for all $\{a_n\}$.
• $a_n \sim b_n$ if and only if $b_n \sim a_n$
• $a_n \sim b_n$ and $b_n \sim c_n$ implies that $a_n \sim c_n$.

A concept similar to asymptotic equality is that of eventually true statements. We say that a predicate $P(n)$ eventually holds if it holds for sufficiently large $n$. That is,

$(\exists n_0)(\forall n \ge n_0) P(n)$

For instance, the sequence $2,3,2,1,1,1,\ldots$ is eventually constant (at some point, they are all ones).

Exercise 54

If a sequence $\{a_n\}$ is eventually constant, then it converges.

The converse of the above exercise is false, e.g., the sequence $a_n = 1+1/n$ converges to one, but it is not eventually constant.

Footnotes

1. Previously we proved that $a_n < 2$. Analogously we can prove that $a_n \ge 1$. ↩