This site is devoted to mathematics and its applications. Created and run by Peter Saveliev.

Sequences and their limits

From Mathematics Is A Science

Jump to: navigation, search

1 What is calculus about?

The idea of calculus in a single picture:

Speedometer-odometer.png

Let's be more specific. We consider two situations.

First, imagine that our speedometer is broken. What do we do, if we want to estimate how fast we are driving? We look at the odometer several times -- say, every hour -- during the trip and record the mileage on a piece of paper. The list of our consecutive locations might look like this:

  • initial reading: $10,000$ miles;
  • after the first hour: $10,055$ miles;
  • after the second hour: $10,095$ miles;
  • after the third hour: $10,155$ miles;
  • etc.

Let's plot the location against time:

Location as a function of time.png

But what do we know about the speed? Nothing without algebra! The algebra is simple; we use the well-known formula: $$\text{ speed }= \frac{\text{ distance }}{\text{ time }}.$$ The time period was chosen to be $1$ hour, so we need only to look at the distance covered during each of these one-hour periods:

  • distance covered during the first hour: $10,055-10,000=55$ miles;
  • distance covered during the second hour: $10,095-10,055=40$ miles;
  • distance covered during the third hour: $10,155-10,095 =60$ miles;
  • etc.

This is how these new numbers appear in the original plot (top):

Location and velocity as functions of time.png

We also plot these new numbers against time (bottom). As you can see, we treat the outcome data as if the speed remains constant during each of these hour-long periods.

The problem is solved! Only within the information provided by the data but we have established that the speed has been -- roughly -- $55$, $40$, and $60$ miles an hour.

Now the opposite problem... Imagine this time that it is the odometer that is broken. If now we want to estimate how far we will have gone, we should look at the speedometer several times -- say, every hour -- during the trip and record its readings on a piece of paper. The result may look like this:

  • during the first hour: $35$ miles an hour;
  • during the second hour: $65$ miles an hour;
  • during the third hour: $50$ miles an hour;
  • etc.

Let's plot our speed against time:

Velocity as a function of time.png

Now, what does this tell us about our location? Nothing, without algebra! We use the same formula: $$\text{ distance }=\text{ speed }\times \text{ time }.$$ In contrast to the first example, we need more information though. We must know where our trip started, say, the $100$ mile mark. The time period was chosen to be $1$ hour, so that we need only to add the speed at which -- we assume -- we drove during each of these one-hour periods:

  • the location after the first hour: $100+35=135$ mile mark;
  • the location after the two hours: $135+65=200$ mile mark;
  • the location after the three hours: $200+50=250$ mile mark;
  • etc.

This is how these new numbers appear in the plot:

Velocity and location functions of time.png

The problem is solved! Only within the information provided by the data but we have established that we have progressed through -- roughly -- $135$, $200$, and $250$ miles marks during this time.

We next consider more complex examples. Here our ability to use negative numbers allows us to treat the data the same way even when we are moving in the opposite direction. In this case, we are dealing with the velocity instead of the speed.

First, from location to velocity... Suppose that this time we have $30$ data points; they are the locations of a moving object recorded every minute: $$\begin{array}{l|l|llllllllll} \text{ location } & \text{ miles } & 0.00 &0.10 &0.20 &0.30 &0.39 &0.48 &0.56 &0.64 &0.72 &0.78 &0.84 &...\\ \hline \text{ time } & \text{ min } &0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &... \end{array}$$ This data is seen in the first two columns of the spreadsheet:

Location excel.png

The data is furthermore illustrated as a “scatter plot” on the right.

To understand how fast we move over these one-minute intervals, we compute the differences of locations for each pair of consecutive locations: $$\begin{array}{l|l|llllllllll} \text{ velocity } & \text{ miles/min } &- &0.10 &0.10 &0.10 &0.09 &0.09 &0.09 &0.08 &0.07 &0.07 &0.06 &...\\ \text{ location } & \text{ miles } &0.00 &0.10 &0.20 &0.30 &0.39 &0.48 &0.56 &0.64 &0.72 &0.78 &0.84 &...\\ \hline \text{ time } & \text{ min } &0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &... \end{array}$$ Practically, we use the spreadsheet with the following formula for each entry in the second column: $$\texttt{ =RC[-1]-R[-1]C[-1]}.$$

Velocity from location.png

This new data is illustrated as the second scatter plot. To emphasize the fact that the velocity data, unlike the location, is referring to time intervals rather than time instances, we plot it with horizontal segments. In fact, the data table can be rearranged as follows to make this point clearer: $$\begin{array}{l|c|c|c|c|c|c|c|c|c|c} \text{ velocity } &\cdot&0.10& \cdot&0.10& \cdot&0.10& \cdot&0.09& \cdot&0.09 &...\\ \text{ location } &0.00 &-&0.10 &-&0.20 &-&0.30 &-& .39&-&...\\ \hline \text{ time } &0 &&1 &&2 &&3 &&4 &&... \end{array}$$

What has happened to the moving object can now be easily read from the second graph:

  • the velocity was positive initially and it was moving in the positive direction;
  • it was moving fairly fast but then started to slow down;
  • it stopped for a very short period;
  • then the velocity became negative as it started to move in the opposite direction;
  • it started to speed up in that direction.

Thus, the latter set of data succinctly records some facts about the qualitative and quantitative behavior of the former. As the latter is derived from the former, the transition is described by: $$\text{function} \quad \longrightarrow \quad \text{its derivative}.$$

Now, from velocity to location... Again, we consider $30$ data points. They are the velocity of an object recorded every minute: $$\begin{array}{l|l|llllllllll} \text{ velocity }&\text{ miles }&0.00 &0.10 &0.20 &0.30 &0.39 &0.48 &0.56 &0.64 &0.72 &0.78 &0.84 &...\\ \hline \text{ time } &\text{ min } &0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &... \end{array}$$ This data is seen in the first two columns of the spreadsheet:

Velocity excel.png

The data is furthermore illustrated as a scatter plot on the right. Again, we emphasize the fact that the velocity data is referring to time intervals and plot it with horizontal bars.

To find out where we are at the end of each of these one-minute intervals, we compute the sums of the velocities, one minute at a time: $$\begin{array}{l|l|llllllllll} \text{ location } &\text{ miles/min } &0.00 &0.10 &0.30 &0.59 &0.98 &1.46 &2.03 &2.67 &3.39 &4.17 &...\\ \text{ velocity } &\text{ miles } &-&0.00 &0.10 &0.20 &0.30 &0.39 &0.48 &0.56 &0.64 &0.72 &...\\ \hline \text{ time } &\text{ min } &0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &... \end{array}$$ Practically, we use a spreadsheet with a formula for each row: $$\texttt{ =R[-1]C+RC[-1]}.$$

Location from velocity.png

The data is also illustrated as the second scatter plot on the right.

We again rearrange the data table to make the difference between two types of data clearer: $$\begin{array}{l|c|c|c|c|c|c|c|c|c|c} \text{ location } &0.00 &-&0.10 &-&0.30 &-&0.59&-& .98&-&...\\ \text{ velocity } &\cdot&0.00& \cdot&0.10& \cdot&0.20& \cdot&0.30& \cdot&0.39 &...\\ \hline \text{ time } &0 &&1 &&2 &&3 &&4 &&... \end{array}$$

Thus, as the former data set records some facts about the quantitative behavior of the latter, we are able to combine this information to recover the latter. This backward transition is described by: $$\text{function} \quad \longrightarrow \quad \text{its antiderivative.}$$

The terminology is justified by the fact that the two operations we have considered undo the effect of each other: $$\text{location} \quad \longrightarrow \quad \text{velocity} \quad \longrightarrow \quad \text{same location (up to initial position),} $$ and $$\text{velocity} \quad \longrightarrow \quad \text{location (up to initial position)} \quad \longrightarrow \quad \text{same velocity.} $$

We can further increase the number of data points and, as we zoom out, the scatter plots will look like continuous curves! We now use what we understand about the behavior of the motion data in those tables to describe continuous motion. We simply look at the slope of the graph:

Slopes as velocities.png

Here we even replace our dependent variable, location, for another, temperature. The results are just as applicable to any other quantity that depends on time, or any other quantity.

Exercise. Your location is recorded every half-hour, shown below. Estimate your velocity as a function of time. $$\begin{array}{r|c} \text{time, }x&\text{location, }y\\ \hline 0&20\\ .5&30\\ 1&20\\ 1.5&20\\ 2&50\\ \end{array}$$

2 Sequences

The lists of numbers in the last section are sequences: the locations and the velocities. Sequences also come from many other sources. A ping-pong ball bouncing off the floor produces a list of heights it reaches:

TT ball bounce.png

Remember that sequences are just functions. After all, both can be -- fully or partially -- represented by tables of numbers: $$\begin{array}{c|c} x&y=x^2\\ \hline 0&0\\ 1&1\\ 2&4\\ 3&9\\ \vdots&\vdots \end{array} \quad\quad\quad \begin{array}{c|c} n&y=n^2\\ \hline 0&0\\ 1&1\\ 2&4\\ 3&9\\ \vdots&\vdots \end{array}$$

Squared.png

Recall also that every function $y=f(x)$ with an appropriate domain, such as the reals, creates a sequence: $$a_n=f(n).$$

A function defined on a ray in the set of integers, $\{p,p+1,...\}$, is called an infinite sequence, or simply sequence, typically given by its formula: $$a_n=\{a_n\}=\{a_n=1/n:\ n=1,2,3,...\},$$ with the abbreviated notation on the left. For example, these are the possibilities: $$a_n=1/n,\ \{1/n\},\ \{a_n=1/n:\ n=1,2,3,...\}.$$

We could visualize sequences by their graphs:

Sequences on the xy-plane.png

However, we will later apply what we have learned about sequences to our study of functions. This is why we take a different approach. First, our visualizations of graphs of sequences will use the re-named Cartesian coordinate system:

  • the horizontal axis is the $n$-axis, and
  • the vertical axis is the $x$-axis.
Sequences on the x-axis.png

Second, we may choose to concentrate on the $x$-axis. This approach allows us to have a more compact way to visualize sequences. For example, they may be locations of a moving object captured at different moments of time.

Just as all functions, sequences are subject to algebraic operations: addition, subtraction, multiplication, and division (Chapter 2). They produce new sequences. However, there are two operations that also produce new sequences that tell us a lot about the original sequence. We saw them in the last section: differences and sums.

The difference represents the change of the sequence, from any of its elements to the next.

Difference of sequence.png

If the sequence represents the location, the difference represents the displacement as discussed in the last section.

Definition. For a sequence $\{a_n\}$, its difference is a new sequence defined and denoted by: $$\Delta_n a_n=a_{n+1}-a_n.$$

Example. For example, an arithmetic progression has a constant difference, by definition: $$\Delta_n (a_0+bn)=a_{n+1}-a_n=(a_0+b(n+1))-(a_0+bn)=b.$$ $\square$

Example. We can also notice that the difference of a geometric progression with $a_0>0$ is positive and increasing when its ratio $r$ is larger than $1$: $$\Delta_n (a_0r^n)=a_{n+1}-a_n=a_0r^{n+1}-a_0r^n=a_0r^n(r-1).$$ It is negative and decreasing when $0<r<1$. $\square$

Recall from the last section how we represented the sum of a sequence: $$\underbrace{a_{1}}_{\text{1 step}} + \underbrace{a_{2}}_{\text{2 step}} + ... + \underbrace{a_{i}}_{i\text{ step}} + ... + \underbrace{a_{n}}_{n\text{ step}}. $$ This is repetitive and cumbersome.

The notation for the sum of a segment -- from $m$ to $n$ -- of a sequence $\{a_i\}$ is chosen to be: $$a_m+a_{m+1}+...+a_n =\sum_{i=m}^{n}a_i.$$ Here $\Sigma$ stands for “S” meaning “sum”. This is how the notation is deconstructed: $$\begin{array}{rlrll} \text{beginning}&\text{and end values for }k\\ \downarrow&\\ \begin{array}{r}3\\ \\k=0\end{array}&\sum \big(\quad k^2 + k \quad\big) &=&20\\ &\qquad\qquad\uparrow&&\uparrow\\ &\qquad\text{a specific sequence}&&\text{a specific number} \end{array}$$ It is called the sigma notation.

The notation applies to all sequences, both finite and infinite.

Example. For example, this is how we contract the summation: $$1^2 + 2^2 + 3^2 + ... + 17^2 = \sum_{k=1}^{n} k^2.$$ It is only possible if we find the $n$th term formula for the sequence: $a_k=k$. And this is how we expand back from this compact notation, by plugging the values of $k=1,2,...,17$ into the formula: $$\sum_{k=1}^{17} k^2 = \underbrace{1^2}_{k=1} + \underbrace{2^2}_{k=2} + \underbrace{3^2}_{k=3} + ... + \underbrace{17^2}_{k=17}.$$ Similarly, $$1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+...+\frac{1}{32}=\sum_{i=0}^{5} \frac{1}{2^k}.$$ $\square$

Sum of sequence.png

Definition. For a sequence $\{a_n:\ n=p,p+1,...\}$, its sum is a new sequence $\{b_n\}$ defined and denoted for each $q\ge p$ within the domain of $a_n$ by a recursive formula: $$b_{n+1}=b_n+a_n;$$ in other words, we have: $$b_q=\sum_{n=p}^q a_n=a_{p}+a_{p+1}+...+a_q.$$

The sequences that come as sums of infinite sequences are called series. They are discussed in Chapter 14.

There are a few shortcut properties of such sums.

The associativity and commutativity of addition produce the following rule.

Theorem (Sum Rule). $$\sum\limits_{i=m}^{n} \left( a_{i} + b_{i} \right) = \sum\limits_{i=m}^{n} a_{i} + \sum\limits_{i=m}^{n} b_{i}.$$

The distributive property takes the following form.

Theorem (Constant Multiple Rule). $$\sum\limits_{i=m}^{n} \left( c\cdot a_{i} \right) = c\cdot \sum\limits_{i=m}^{n} a_{i}.$$

There is no (as simple as these) product rule as the product of a sum with $n$ terms and one with $m$ terms will have $nm$ terms.

Comparing the illustrations above we discover that the two operations -- the difference and the sum -- undo the effect of each other:

FTDC.png

This idea will be developed in Chapter 10 into the so-called Fundamental Theorem of Calculus.

Note that if the sequence is integer-valued then so are its difference and its sum.

3 Limits of sequences: long-term trends

We will study infinite sequences of numbers and especially their trends. The idea is simple: $$\begin{array}{llllllll} \text{sequence }&1&1/2&1/3&1/4&1/5&...&\text{ trends toward } 0;\\ \text{sequence }&.9&.99&.999&.9999&.99999&...&\text{ trends toward } 1;\\ \text{sequence }&1&2&3&4&5&...&\text{ trends toward } \infty;\\ \text{sequence }&0&1&0&1&0&...&\text{ has no trend}. \end{array}$$ In other words, an infinite sequence of numbers will be sometimes “accumulating” around a single number. The gap between the bouncing ball and the ground becomes invisible!

Even though every function $y=f(x)$ with an appropriate domain creates a sequence, $a_n=f(n)$, the converse isn't true. This discrepancy serves our purpose: the primary, if not the only, reason for studying sequences is to understand (their) trends, called limits.

A function defined on a ray in the set of integers, $\{p,p+1,...\}$, is called an infinite sequence, or simply sequence, typically given by its formula: $$a_n=\{a_n\}=\{a_n=1/n:\ n=1,2,3,...\},$$ with the abbreviated notation on the left. For example, these are the possibilities: $$a_n=1/n,\ \{1/n\},\ \{a_n=1/n:\ n=1,2,3,...\}.$$

We could visualize sequences as the graphs of functions:

Sequences on the xy-plane.png

However, we take a different approach; we will apply, at a later time, what we have learned about sequences to our study of functions. This is why our visualizations of graphs of sequences will use the re-named Cartesian coordinate system:

  • the horizontal axis is the $n$-axis, and
  • the vertical axis is the $x$-axis.
Sequences on the x-axis.png

This approach allows us to have a more compact way to visualize sequences (right) as sequences of points on the $x$-axis.

Example. The go-to example is that of the sequence of the reciprocals: $$x_n=\frac{1}{n}.$$ It tends to $0$.

Reciprocals.png

This fact is easy to confirm numerically: $$x_n=1.000,\ 0.500,\ 0.333,\ 0.250,\ 0.200,\ 0.167,\ 0.143,\ 0.125,\ 0.111,\ ... $$ $\square$

Example. However, numerical analysis alone can't be used for discovering the value of the limit. Plotting the first $1000$ terms of the sequence $x_n=n^{-.01}$ fails to suggest the true value of the limit:

Geometric progression slow convergence 1000.png

In fact, it is zero. $\square$

Example. Sequences are ubiquitous. For example, given a real number, we can easily construct a sequence that tends to that number -- via its decimal approximations. For example, $$x_n=0.3,\ 0.33,\ 0.333,\ 0.3333,\ ... \text{ tends to } 1 / 3 .$$

One third decimal.png

$\square$

Example. The values can also approach the ultimate destination from both sides, such as $$x_n=(-1)^n\frac{1}{n}.$$

Reciprocals alternating.png

$\square$

The notation for limits is the following: $$a_n \to a \text{ as } n\to \infty,$$ as well as $$\lim_{n\to\infty} a_n=a.$$ We will include the possibility of infinite limits: $$a_n \to \infty \text{ as } n\to \infty,$$ and $$\lim_{n\to\infty} a_n=\infty.$$

Exercise. What can you say about the limit of an integer-valued sequence?

Example (Zeno's paradox). Consider a simple scenario: as you walk toward a wall, you can never reach it because once you've covered half the distance, there is still distance left, etc.

Zeno.png

We mark these steps and do observe that there are infinitely many of them to be taken... $\square$

4 The definition of limit

Calculus, for a large part, is the study of how to properly handle infinity.

Example. Let's examine this seemingly legitimate computation: $$\begin{array}{cccccc} 0& \overset{\text{?}}{=\! =\! =} &0&&+0&&+0&&+0&&+...\\ & \overset{\text{?}}{=\! =\! =} &(1&-1)&+(1&-1)&+(1&-1)&+(1&-1)&+...\\ & \overset{\text{?}}{=\! =\! =} &1&-1&+1&-1&+1&-1&+1&-1&+...\\ & \overset{\text{?}}{=\! =\! =} &1&+(-1&+1)&+(-1&+1)&+(-1&+1)&+(-1&+1)&...\\ & \overset{\text{?}}{=\! =\! =} &1&+0&&+0&&+0&&+0&&+...\\ & \overset{\text{?}}{=\! =\! =} &1. \end{array}$$ That's impossible! How did this happen? One can say that we got something from nothing (the numbers refer to the amount of soil taken out):

Something from nothing divergent.png

The problem is that we casually carried out infinitely many algebraic operations. $\square$

Exercise. Which of the “$=$” signs above is incorrect?

Thus, when facing infinity, algebra may fail. But it doesn't have to... when the sequence has a limit! A limit is a number and the sequence approximates this number: $$\begin{array}{llllllll} \text{ sequence }&1&1/2&1/3&1/4&1/5&...&\text{ approximates }0;\\ \text{ sequence }&.9&.99&.999&.9999&.99999&...&\text{ approximates }1;\\ \text{ sequence }&1.&1.1&1.01&1.001&1.0001&...&\text{ approximates }1;\\ \text{ sequence }&3.&3.1&3.14&3.141&3.1415&...&\text{ approximates }\pi;\\ \text{ sequence }&1&2&3&4&5&...&\text{ approaches } \infty;\\ \text{ sequence }&0&1&0&1&0&...&\text{ doesn't approximate any number}. \end{array}$$ In other words, we can substitute the sequence for the number it approximates and do it with any degree of accuracy!

Now, let's find the exact meaning of limit.

Geometrically, we see how the sequence accumulates toward a particular horizontal line:

Reciprocals.png

At the end, the dots can't be distinguished from the $x$-axis.

Example. We have a more concise illustration if we concentrate on the $y$-axis only:

Sequence accumulation.png

We can see that after sufficiently many steps, the elements of the sequence, $a_n$, become indistinguishable from the limit, $a$. It seems that, say, the $10$th dot has merged with $a$. $\square$

Example. Let's now look at this “process” numerically. What does it mean that $a_n=1/n^2$ approaches $a=0$?

First, how long does it take to get within $.1$ from $a$? Look up in the table of values: it takes $4$ steps.

Limit of 1x2 is 0.png

Second, how long does it take to get within $.01$ from $a$? It takes $11$ steps.

Third, how long does it take to get within $.001$ from $a$? It takes $32$ steps.

And so on. No matter how small a number I pick, eventually $a_n$ will be that close to its limit. $\square$

Example. Another interpretation of this analysis is in terms of accuracy. We understand the idea that $a_n=1/n^2$ approaches $a=0$ as : “the sequence approximates $0$”.

First, what if we need the accuracy to be $.1$? Look up in the table of values: we need to compute $4$ terms of the sequence or more.

Second, what if we need the accuracy to be $.01$? At least $11$ terms.

Third, what if we need the accuracy to be $.001$? At least $32$.

And so on. No matter how much accuracy I need, there is a way to accommodate this requirement by getting farther and farther into the sequence $a_n$. $\square$

Unfortunately, not all sequences are as simple as that. They may approach their respective limits in a number of ways, as we have seen. They don't have to be monotone:

Non-monotone sequence.png

They might approach the limit from above and below at the same time:

Reciprocals alternating.png

And so on... And then there are sequences with no limits. We need a more general approach.

We re-write what we want to say about the meaning of the limits in progressively more and more precise terms. $$\begin{array}{l|ll} n&y=a_n\\ \hline \text{As } n\to \infty, & \text{we have } y\to a.\\ \text{As } n\text{ approaches } \infty, & y\text{ approaches } a. \\ \text{As } n \text{ is getting larger and larger}, & \text{the distance from }y \text{ to } a \text{ approaches } 0. \\ \text{By making } n \text{ larger and larger},& \text{we make } |y-a| \text{ as small as needed}.\\ \text{By making } n \text{ larger than some } N>0 ,& \text{we make } |y-a| \text{ smaller than any given } \varepsilon>0. \end{array}$$

The absolute values above are the distances from $a_n$ to $a$, as shown below:

Definition of limit 2.png

Algebraically, we see that for every measure of “closeness”, call it $\varepsilon$, the function's values become eventually that close to the limit. In other words, $\varepsilon$ is the degree of required accuracy.

Example. Let's prove this statement for the sequence from the last example, $a_n=1/n^2$. Let's imagine that any degree of accuracy $\varepsilon>0$ that needs to be accommodated is supplied ahead of time. Let's find such an $n$ that $a_n$ is within $\varepsilon$ from $a=0$. In other words, we need this inequality to be satisfied: $$|a_n-a|=\left| \frac{1}{n^2}-0 \right|=\frac{1}{n^2}<\varepsilon.$$ We solve it: $$n>\frac{1}{\sqrt{\varepsilon}}=N.$$ This proves that the requirement can be satisfied. Then, for any such $n$ we have $|a_n-a|<\varepsilon$, as required.

The result gives us the same answers for the three particular choices of $\varepsilon =.1,\ .01,\ .001$ from the last example, as well as for any other... For example, let's pick $\varepsilon=.0001$, what is $N$? By the formula, it is $$N= \frac{1}{\sqrt{.0001}} =\frac{1}{\left( 10^{-4}\right)^{1/2}} = \frac{1}{ 10^{-2} } =10^2=100.$$ $\square$

Exercise. Carry out such an analysis for $a_n=1/\sqrt{x}$.

Definition. We call number $a$ the limit of the sequence $a_n$ if the following condition holds:

  • for each real number $\varepsilon > 0$, there exists a number $N$ such that, for every natural number $n > N$, we have

$$|a_n - a| < \varepsilon .$$ We also say that the limit is finite. If a sequence has a limit, then we call the sequence convergent and say that it converges; otherwise it is divergent and we say it diverges.

Example. Let's apply the definition to $$a_n=1+\frac{(-1)^n}{n}.$$ Suppose an $\varepsilon>0$ is given. Looking at the numbers, we discover that they accumulate toward $1$. Is this the limit? We apply the definition. Let's find such an $n$ that $a_n$ is within $\varepsilon$ from $a=1$: $$|a_n-a|=\left| 1+\frac{(-1)^n}{n}-1 \right|=\left| \frac{(-1)^n}{n} \right|=\frac{1}{n}<\varepsilon.$$ We solve it: $$n>\frac{1}{\varepsilon}.$$ That gives us the $N$ required by the definition; we let $$N= \frac{1}{\varepsilon} .$$ Then, for any $n>N$ we have $|a_n-a|<\varepsilon$, as required by the definition. $\square$

Another way to visualize a trend in a convergent sequence is to enclose the end of the tail of the sequence in a band:

Definition of limit.png

It should be, in fact, a narrower and narrower band; its width is $2\varepsilon$. Meanwhile, the starting point of the band moves to the right; that's $N$.

Examples of divergence are below.

Example. A sequence may tend to infinity, such as $a_n=n$:

Identity sequence.png

Then no band -- no matter how wide -- will contain the sequence's tail. $\square$

This behavior however has a meaningful pattern.

Definition. We say that a sequence $a_n$ tends to positive infinity if the following condition holds:

  • for each real number $R$, there exists a natural number $N$ such that, for every natural number $n > N$, we have

$$a_n >R.$$ We say that a sequence $a_n$ tends to negative infinity if:

  • for each real number $R$, there exists a natural number $N$ such that, for every natural number $n > N$, we have

$$a_n <R.$$ In either case, we also way that the limit is infinite.

We describe such a behavior with the following notation: $$a_n\to \pm\infty \text{ as } n\to \infty ,$$ or $$\lim_{n\to \infty}a_n=\pm\infty.$$

Example. Some sequences seem to have no pattern at all, such as $a_n=\sin n$:

Sin n.png

Here, a band -- if narrow enough -- can contain the sequence's tail.

If, however, we also divide this expression by $n$, the swings start to diminish:

Graph 1nsinn.png

The limit is $0$! $\square$

Example. The next example is $a_n=1+(-1)^n+\frac{1}{n}$. It seems to approach two limits at the same time:

Uniqueness of limit.png

Indeed, no matter how narrow, we can find two bands to contain the sequence's two tails. However, no single band -- if narrow enough -- will contain them! $\square$

Example. Let's pick a simpler sequence and do this analytically. Let $$a_n=(-1)^n=\begin{cases} 1&\text{ if } n \text{ is even,}\\ -1&\text{ if } n \text{ is odd.} \end{cases}$$ Is the limit $a=1$? If it is, then this is what needs to be “small”: $$|a_n-a|=\left| (-1)^n-1 \right|=\begin{cases} 0&\text{ if } n \text{ is even,}\\ 2&\text{ if } n \text{ is odd.} \end{cases}$$ It's not! Indeed, this expression won't be less than $\varepsilon$ if we choose it to be, say, $1$, no matter what $N$ is. So, $a=1$ is not the limit. Is $a=-1$ the limit? Same story. In order to prove the negative, we need to try every possible value of $a$. $\square$

Exercise. Finish the proof in the last example.

Example. For a given real number, we can construct a sequence that approximates that number -- via truncations of its decimal approximations. For example, we have already seen this: $$x_n=0.9 , 0.99 , 0.999 , 0.9999 , . . . \text{ tends to } 1 .$$ Furthermore, we have: $$x_n=0.3 , 0.33 , 0.333 , 0.3333 , . . . \text{ tends to } 1 / 3 .$$ The idea of limit then helps us understand infinite decimals.

  • What is the meaning of $.9999...$? It is the limit of the sequence $0.9 , 0.99 , 0.999, ...$; i.e., $1$.
  • What is the meaning of $.3333...$? It is the limit of the sequence $0.3 , 0.3 , 0.333, ...$; i.e., $1/3$.

$\square$

Exercise. Find the formulas for the two sequences above and confirm the limits.

We need to justify “the” in “the limit”.

Theorem (Uniqueness). A sequence can have only one limit (finite or infinite); i.e., if $a$ and $b$ are limits of the same sequence, then $a=b$.

Proof. The geometry of the proof is clear: we want to separate the two horizontal lines representing two potential limits by two non-overlapping bands, as shown above. Then the tail of the sequence would have to fit one or the other, but not both. These bands correspond to two intervals around those two “limits”. In order for them to be disjoint, their width (that's $2\varepsilon$!) should be less than half the distance between the two numbers.

Proof of uniqueness of limit of sequence.png

The proof is by contradiction. Suppose $a$ and $b$ are two limits, i.e., either satisfies the definition, and suppose also $a\ne b$. In fact, without loss of generality we can assume that $a<b$. Let $$\varepsilon = \frac{b-a}{2}.$$ Then, what we are going to use at the end is $$a+\varepsilon=b-\varepsilon.$$

Now, we rewrite the definition for $a$ and $b$ specifically:

  • there exists a number $L$ such that, for every natural number $n > L$, we have

$$|a_n - a| < \varepsilon .$$ Now, we rewrite the definition for $M$ as limit:

  • there exists a number $M$ such that, for every natural number $n > M$, we have

$$|a_n - b| < \varepsilon .$$ In order to combine the two statements, we need them to be satisfied for the same values of $n$. Let $$N=\min\{ L,M\}.$$ Then,

  • for every number $n > N$, we have

$$|a_n - a| < \varepsilon ,$$

  • for every number $n > N$, we have

$$|a_n - b| < \varepsilon .$$ In particular, for every $n > N$, we have: $$ a_n < a+\varepsilon=b-\varepsilon<a_n.$$ A contradiction. $\blacksquare$

Exercise. Follow the proof and demonstrate that that it is impossible to for a sequence to have as limit: (a) a real number and $\pm\infty$, or (b) $-\infty$ and $+\infty$.

The theorem indicates that the correspondence:

  • a convergent sequence $\longrightarrow$ its limit (a real number),

makes sense. Can we reverse this correspondence? No, because there are many sequences converging to the same number. However, we can say that a real number “is” its approximations, i.e., all sequences that converge to it.

Thus, there can be no two limits and we are justified to speak of the limit.

The limits of some specific sequences can be easily found.

Theorem (Constant). For any real $c$, we have $$\lim_{n \to \infty}c = c.$$

Theorem (Arithmetic progression). For any real numbers $m,b>0$, we have $$\lim_{n \to \infty}(b+nm) = \begin{cases} -\infty &\text{ if } m<0,\\ b &\text{ if } m=0,\\ +\infty &\text{ if } m>0. \end{cases}$$

Exercise. Prove the theorem.

Theorem (Powers). For any integer $k$, we have $$\lim_{n \to \infty}n^k = \begin{cases} 0&\text{ if } k<0,\\ 1&\text{ if } k=0,\\ +\infty&\text{ if } k>0. \end{cases}$$

Proof. First, the case of $k<0$. Suppose $\varepsilon >0$ is given. We need to find such an $N$ that $|n^k-0|=n^k<\varepsilon$ whenever $n>N$. We can express such an $N$ in terms of this $\varepsilon$; we just choose: $$N= \sqrt[1/k]{\varepsilon}.$$

Second, the case of $k<0$. Suppose $R>0$ is given. We need to find such an $N$ that $n^k>R$ whenever $n>N$. We can express such an $N$ in terms of this $R$; similarly to the above we choose: $$N= \sqrt[1/k]{R}.$$ $\blacksquare$

Theorem (Geometric progression). For any real number $r$, we have $$\lim_{n \to \infty}r^n = \begin{cases} \text{diverges } &\text{ if } r \le -1,\\ 0 &\text{ if } |r|<1,\\ 1 &\text{ if } r=1,\\ +\infty &\text{ if } r>1. \end{cases}$$

Exercise. Prove the theorem.

Example. Geometric progressions are used to model population growth and decline. $\square$

Exercise. Find the limits of each of these sequences or show that it doesn't exist:

  • (a) $1,\ 3,\ 5,\ 7,\ 9,\ 11,\ 13,\ 15,\ ...$;
  • (b) $.9,\ .99,\ .999,\ .9999,\ ...$;
  • (c) $1,\ -1,\ 1,\ -1,\ ...$;
  • (d) $1,\ 1/2,\ 1/3,\ 1/4,\ ...$;
  • (e) $1,\ 1/2,\ 1/4\ ,1/8,\ ...$;
  • (f) $2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ ...$;
  • (g) $1,\ -4,\ 9,\ -16,\ 25,\ ...$;
  • (h) $3,\ 1,\ 4,\ 1,\ 5,\ 9,\ ...$.

5 Algebra of sequences and limits

If every real number is the sequence of its approximations, does algebra with these numbers still make sense? Fortunately, limits behave well with respect to the usual arithmetic operations. Below we assume that the sequences are defined on the same set of integers.

We will study convergence of sequences with the help of other, simpler, sequences. The theorem below shows why.

Theorem. $$a_n\to a \ \Longleftrightarrow\ |a_n-a|\to 0.$$

A n--a iff a n-a--0.png

Then to understand limits of sequences in general, we need first to understand those of a smaller class:

  • positive sequences that converge to $0$.

The definition of convergence becomes simpler:

  • $0<a_n\to 0$ when for any $\varepsilon >0$ there is $N$ such that $a_n<\varepsilon $ for all $n>N$.

We start with addition.

Sum Rule for sequences 0.png

To graphically add two sequences, we flip the second upside down and then connect each pair of dots with a bar. Then, the lengths of these bars form the new sequence. Now, if either sequence converges to $0$, then so do these bars.

Theorem (Sum Rule). $$0<a_n\to 0,\ 0<b_n\to 0 \ \Longrightarrow\ a_n+ b_n\to 0.$$

Proof. Suppose $\varepsilon >0$ is given. From the definition,

  • $a_n\to 0\ \Longrightarrow$ there is $N$ such that $a_n<\varepsilon /2$ for all $n>N$, and
  • $b_n\to 0\ \Longrightarrow$ there is $M$ such that $b_n<\varepsilon /2$ for all $n>M$.

Then for all $n>\max\{N,M\}$, we have $$a_n+b_n<\varepsilon /2+\varepsilon /2 =\varepsilon .$$ Therefore, by definition $a_n+ b_n\to 0$. $\blacksquare$

Exercise. Prove the version of the above theorem for $m$ sequences (a) from the theorem and (b) by generalizing the proof.

Multiplying a sequence by a constant number simply stretches the whole picture in the vertical direction -- in both directions, away from the $z$-axis.

Constant Multiple Rule for sequences 0.png

Then, zero remains zero!

Theorem (Constant Multiple Rule). $$0<a_n\to 0 \ \Longrightarrow\ ca_n\to 0 \text{ for any real }c>0.$$

Proof. Suppose $\varepsilon >0$ is given. From the definition,

  • $0 < a_n\to 0\ \Longrightarrow$ there is $N$ such that $a_n <\varepsilon /c$ for all $n>N$.

Then for all $n>N$, we have $$c\cdot a_n < c\cdot \varepsilon /c=\varepsilon .$$ Therefore, by definition $ca_n\to 0$. $\blacksquare$

For more complex situations we need to use the fact that convergent sequences are bounded; i.e., the sequence fits into a (not necessary narrow) band.

Theorem (Boundedness). $$a_n\to a \ \Longrightarrow\ |a_n| < Q \text{ for some real } Q.$$

Proof. The idea is that the tail of the sequence does fit into a (narrow) band; meanwhile, there are only finitely many terms left... Choose $\varepsilon =1$. Then by definition, there is such $N$ that for all $n>N$ we have: $$|a_n-a| < 1.$$ Then, we have $$\begin{array}{lll} |a_n|&=|(a_n-a)+a|&\text{ ...then by the Triangle Inequality...}\\ &\le |a_n-a|+|a|&\text{ ...then by the inequality above...}\\ &<1+|a|. \end{array}$$ To finish the proof, we choose: $$Q=\max\{|a_1|,...,|a_N|,1+|a|\}.$$ $\blacksquare$

The proof is illustrated below:

Boundedness for sequences.png

The converse isn't true: not every bounded sequence is convergent. Just try $a_n=\sin n$. We will show later that, with an extra condition, bounded sequences do have to converge...

We are now ready for the general results on the algebra of limits.

Sum Rule for sequences.png

Theorem (Sum Rule). If sequences $a_n ,b_n$ converge then so does $a_n + b_n$, and $$\lim_{n\to\infty} (a_n + b_n) = \lim_{n\to\infty} a_n + \lim_{n\to\infty} b_n.$$

Proof. Suppose $$a_n\to a,\ b_n\to b.$$ Then $$|a_n - a|\to 0, \ |b_n-b|\to 0.$$ We compute $$\begin{array}{lll} |(a_n + b_n)-(a+b)|&= |(a_n-a)+( b_n-b)|& \text{ ...then by the Triangle Inequality...}\\ &\le |a_n-a|+| b_n-b|&\\ &\to 0+0 & \text{ ...by SR...}\\ &=0. \end{array}$$ Then, by the last theorem, we have $$|(a_n + b_n)-(a+b)|\to 0.$$ Then, by the first theorem, we have: $$a_n + b_n\to a+b.$$ $\blacksquare$

When two sequences are multiplied, it is as if we use each pair of their values to build a rectangle:

Product Rule for sequences.png

Then the areas of these rectangles form a new sequence and these areas converge if the widths and the heights converge.

Theorem (Product Rule). If sequences $a_n ,b_n$ converge then so does $a_n \cdot b_n$, and $$\lim_{n\to\infty} (a_n \cdot b_n) = (\lim_{n\to\infty} a_n)\cdot( \lim_{n\to\infty} b_n).$$

Proof. Suppose $a_n\to a,\ b_n\to b$. Then, $$|a_n-1|\to 0,\ |b_n-b|\to 0.$$ Consider, $$\begin{array}{lll} |a_n\cdot b_n-a\cdot b| &= |a_n\cdot b_n+(-a\cdot b_n+a\cdot b_n) -a\cdot b|&\text{ ...adding extra terms then factoring...}\\ &= |(a_n-a)\cdot b_n+a\cdot( b_n - b)|&\text{ ...then by the Triangle Inequality...}\\ &\le |(a_n-a)\cdot b_n|+|a\cdot ( b_n - b)|&\\ &= |a_n-a|\cdot |b_n|+|a|\cdot | b_n - b|&\text{ ...then by Boundedness...}\\ &\le |a_n-a|\cdot Q+|a|\cdot | b_n - b|&\\ &\to 0\cdot Q+|a|\cdot 0&\text{ ...by SR and CMR...}\\ &=0. \end{array}$$ Therefore, $$a_n\cdot b_n \to a\cdot b.$$ $\blacksquare$

CMR follows.

Theorem (Constant Multiple Rule). If sequence $a_n $ converges then so does $c a_n$ for any real $c$, and $$\lim_{n\to\infty} c\, a_n = c \cdot \lim_{n\to\infty} a_n.$$

Example. These laws help us justify the following trick of finding fraction representations of infinite decimals. This is how we deal with $x=.3333...$: $$\begin{array}{llll} x&=0.3333...\\ -\\ 10x&=3.3333...\\ \hline -9x&=-3.0000...\\ &&&&&&&&\Longrightarrow\ x=1/3 \end{array}$$ Instead we use the Constant Multiple Rule and the Difference Rule to carry out the following algebra of sequences: $$\begin{array}{llll} \{a_n\}:&0&0.3&0.33&0.333&0.3333&...&\to&x\\ -\\ \{10a_n\}:&3&3.3&3.33&3.333&3.3333&...&\to&10x\\ \hline \{-9a_n\}:&-3&-3&-3&-3&-3&...&\to&-9x\\ &&&&&&&&\Longrightarrow\ x=1/3 \end{array}$$ Note that we have shifted the values of the second sequence. $\square$

One can understand division of sequences as multiplication in reverse: if the areas of the rectangles converge and so do their widths, then so do their heights.

Also, when two sequences are divided, it is as if we use each pair of their values to build a triangle:

Quotient Rule for sequences.png

Then the tangents of the base angles of these triangles form a new sequence and they converge if the widths and the heights converge.

Theorem (Quotient Rule). If sequences $a_n ,b_n$ converge then so does $a_n / b_n$ whenever defined, and $$\lim_{n\to\infty} \left(\frac{a_n}{b_n}\right) = \frac{\lim\limits_{n\to\infty} a_n}{\lim\limits_{n\to\infty} b_n},$$ provided $\lim_{n\to\infty} b_n \ne 0.$

Proof. We will only prove the case of $a_n=1$. Suppose $b_n\to b\ne 0$. First, choose $\varepsilon =|b|/2$ in the definition of convergence. Then there is $N$ such that for all $n>N$ we have $$|b_n-b|<|b|/2.$$ Therefore, $$|b_n|>|b|/2.$$ Next, $$\begin{array}{lll} \left| \frac{1}{b_n}-\frac{1}{b} \right| &= \left|\frac{b-b_n}{b_nb} \right|&\\ &= \frac{|b-b_n|}{|b_n|\cdot|b|}&\text{ ...then by above inequality...}\\ &< \frac{|b-b_n|}{|b/2|\cdot|b|}&\\ &\to \frac{0}{|b/2|\cdot|b|}&\text{ ...by the CMR...}\\ &=0. \end{array}$$ Therefore, $$\frac{1}{b_n} \to \frac{1}{b}.$$ Finally, the general case of QR follows from PR: $$\frac{a_n}{b_n}=a_n\cdot \frac{1}{b_n}\to a\cdot \frac{1}{b}=\frac{a}{b}.$$ $\blacksquare$

Exercise. What are the rules of the algebra of infinities for products?

Warning: it is considered a serious error if you use the conclusion (the formula) one of these rules without verifying the conditions (the convergence of the sequences involved).

The summary result below shows that when we replace every real number with a sequence converging to it, it is still possible to do algebraic operations with them.

Theorem (Algebra of Limits of Sequences). Suppose $a_n\to a$ and $b_n\to b$. Then $$\begin{array}{|ll|ll|} \hline \text{SR: }& a_n + b_n\to a + b& \text{CMR: }& c\cdot a_n\to ca& \text{ for any real }c\\ \text{PR: }& a_n \cdot b_n\to ab& \text{QR: }& a_n/b_n\to a/b &\text{ provided }b\ne 0\\ \hline \end{array}$$

Example. Let $$a_n=7n^{-2}+\frac{2}{3^n}+8.$$ What is its limit as $n\to \infty$? The computation is straightforward, but every step has to be justified with the rules above.

To understand which rules to apply first, observe that the last operation is addition. We use SR first, subject to justification: $$\begin{array}{lll} \lim_{n\to \infty}a_n&=\lim_{n\to \infty} (7n^{-2}+\frac{2}{3^n}+8) &\text{ ...use SR}\\ &=\lim_{n\to \infty} (7\cdot n^{-2})+\lim_{n\to \infty}(2\cdot \frac{1}{3^n})+\lim_{n\to \infty}8 &\text{ ...use CMR }\\ &=7\cdot \lim_{n\to \infty} n^{-2} +2\cdot \lim_{n\to \infty}3^{-n}+8 \quad&\\ &=7\cdot 0 +2 \cdot 0 +8\\ &=8. \end{array}$$ As all the limits exist, our use of SR (and then CMR) was justified. $\square$

Example. Prove the limit: $$\lim_{n \to \infty}(n^2-n) = +\infty .$$ Plotting the graph does suggest that the limit is infinite.

Since the last operation is addition, we are supposed to use SR first. However, both of the terms go to $\infty$, which makes SR inapplicable. An attempt to apply SR -- over this objection -- would result in an indeterminate expression: $$ \newcommand{\ra}[1]{\!\!\!\!\!\xrightarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} \begin{array}{ll}n^2-n& \ra{???}& \infty - \infty . \end{array}$$ This expression is meaningless! We can't conclude that the limit doesn't exist, or that is does! We've just failed to find the answer. What should we do? $\square$

Presented verbally, these rules have these abbreviated versions:

  • the limit of the sum is the sum of the limits;
  • the limit of the difference is the difference of the limits;
  • the limit of the product is the product of the limits;
  • the limit of the quotient is the quotient of the limits (as long as the one of the denominator isn't zero).

Warning: never forget to confirm the preconditions before using these rules.

Let's represent the Sum Rule as a diagram: $$\newcommand{\ra}[1]{\!\!\!\!\!\xrightarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\la}[1]{\!\!\!\!\!\xleftarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} \newcommand{\ua}[1]{\left\uparrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} \begin{array}{ccc} a_n,b_n&\ra{\lim}&a,b\\ \ \da{+}&SR &\ \da{+}\\ a_n+b_n & \ra{\lim}&\lim(a_n+b_n)=a+b \end{array} $$ In the diagram, we start with a pair of sequences at the top left and then we proceed in two ways:

  • right: take the limit of either, then down: add the results; or
  • down: add them, then right: take the limit of the result.

The result is the same! For the Product Rule and the Quotient Rule, we just replace “$+$” with “$\cdot$” and “$\div$” respectively.

These rules show why approximations work. Indeed, we can think of a sequence that converges to a number as a sequence of better and better approximations. Then carrying out all the algebra with these sequences will produce the same result as the original computation is meant to produce! For example, here is such a substitution: $$\begin{array}{cccl} (1)&+&(2)&&=&3\\ \left(1+\frac{1}{n}\right)&+&\left(2-\frac{5}{n}\right)&=3-\frac{4}{n}&\to&3 \end{array}$$

What about infinite limits? If we replace an infinity with a sequence that approaches it, will the algebra make sense?

6 Can we add infinities? Subtract? Divide? Multiply?

We have demonstrated that in our computations of limits we can replace any sequence with its limit and continue doing the algebra. This conclusion doesn't apply to divergent sequences!

Sequences that approach infinity diverge, technically, but they provide useful information about the pattern exhibiting by the sequences. Such a sequence can also be a part of another, convergent sequence...

Theorem (Limits of Polynomials). Suppose we have a polynomial of degree $p$ with the leading coefficient $a_p\ne 0$. Then the limit of the sequence defined by this function is: $$\lim_{n\to\infty}(a_pn^p+a_{p-1}n^{p-1}+...+ a_1n+a_0)=\begin{cases} +\infty&\text{ if } a_p>0;\\ -\infty&\text{ if } a_p<0. \end{cases}$$

Proof. The idea is to factor out the highest power: $$a_pn^p+a_{p-1}n^{p-1}+...+ a_1n+a_0=n^p(a_p+a_{p-1}n^{-1}+...+ a_1n^{1-p}+a_0n^{-p})\to +\infty(a_p+0).$$ $\blacksquare$

So, as far as its behavior at $\infty$, for a polynomial,

  • only the leading term matters.

Example. Evaluate the limit: $$\lim_{n \to \infty}\frac{4n^2-n+2}{2n^2-1}.$$

Plotting the graph does suggest that the limit is $a=2$:

Rational sequence with limit.png

Since the last operation is division, so are supposed to use QR first. However, both the numerator and the denominator go to $\infty$. Then, QR is inapplicable. An attempt to apply QR -- against our better judgement -- would result in an indeterminate expression: $$ \newcommand{\ra}[1]{\!\!\!\!\!\xrightarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} \begin{array}{ll}\frac{4n^2-n+2}{2n^2-1}& \ra{???}& \frac{\infty}{\infty}.\end{array}$$

Infinity divided by infinity.png

Once again, we can't conclude that the limit doesn't exist; we've just failed to find the answer. The path out of this conundrum lies through algebra.

We divide the numerator and denominator by $n^2$ : $$\begin{array}{lll} \frac{4n^2-n+2}{2n^2-1}&=\frac{(4n^2-n+2)/n^2}{(2n^2-1)/n^2}\\ &=\frac{4-\tfrac{1}{n}+\tfrac{2}{n^2}}{2-\tfrac{1}{n^2}}\\ &\to\frac{4-0+0}{2-0}\\ &=\frac{4}{2}\\ &=2. \end{array}$$ We only used QR at the very end, after the indeterminacy has been resolved. $\square$

The general method for finding such limits is given by the theorem below.

Theorem (Limits of rational functions). Suppose we have a rational function $f$ represented as a quotient of two polynomials of degrees $p$ and $q$, with the leading coefficients $a_p\ne 0,\ b_q\ne 0$. Then the limit of the sequence defined by this function is: $$\lim_{n\to\infty}\frac{a_pn^p+a_{p-1}n^{p-1}+...+ a_1n+a_0}{b_qn^q+b_{q-1}n^{q-1}+...+ b_1n+b_0}=\begin{cases} \pm\infty&\text{ if } p>q;\\ \frac{a_p}{b_p}&\text{ if } p=q;\\ 0&\text{ if } p<q. \end{cases}$$

Proof. The idea is to divide by the highest power. If $p>q$, we have $$\frac{a_pn^p+a_{p-1}n^{p-1}+...+ a_1n+a_0}{b_qn^q+b_{q-1}n^{q-1}+...+ b_1n+b_0}=\frac{a_p+a_{p-1}n^{-1}+...+ a_1n^{-p+1}+a_0n^{-p}}{b_qn^{q-p}+b_{q-1}n^{q-p-1}+...+ b_1n^{1-p}+b_0n^{-p}}\to\frac{a_p+0}{0}=\pm\infty.$$ If $p=q$, we have $$\frac{a_pn^p+a_{p-1}n^{p-1}+...+ a_1n+a_0}{b_qn^q+b_{q-1}n^{q-1}+...+ b_1n+b_0}=\frac{a_p+a_{p-1}n^{-1}+...+ a_1n^{-p+1}+a_0n^{-p}}{b_q+b_{q-1}n^{-1}+...+ b_1n^{1-p}+b_0n^{-p}}\to\frac{a_p+0}{b_p+0}=\frac{a_p}{b_p}.$$ If $p<q$, we have $$\frac{a_pn^p+a_{p-1}n^{p-1}+...+ a_1n+a_0}{b_qn^q+b_{q-1}n^{q-1}+...+ b_1n+b_0}=\frac{a_pn^{p-q}+a_{p-1}n^{p-q-1}+...+ a_1n^{1-q}+a_0n^{-q}}{b_q+b_{q-1}n^{-1}+...+ b_1n^{-q+1}+b_0n^{-q}}\to\frac{0}{b_q+0}=0.$$ $\blacksquare$

This is the lesson we have re-learned:

  • the long-term behavior of polynomials is determined by their leading terms.

Indeed: $$\lim_{n\to\infty}\frac{a_pn^p+a_{p-1}n^{p-1}+...+ a_1n+a_0}{b_qn^q+b_{q-1}n^{q-1}+...+ b_1n+b_0}=\lim_{n\to\infty}\frac{a_pn^p}{b_qn^q}=\frac{a_p}{b_q}\lim_{n\to\infty}n^{p-q}.$$

Example. Find the limit of the sequence: $$\begin{array}{lll} y_n&=\frac{1+(-3)^n}{5^n} & \leadsto\text{ QR? } \text{ But the numerator diverges -- DEAD END! }\\ &=\frac{1}{5^n}+\frac{(-3)^n}{5^n}\\ &=\left( \frac{1}{5} \right)^n + \left( \frac{-3}{5} \right)^n \\ &\quad\quad \downarrow \quad\quad\quad\quad \downarrow\\ &\quad\quad 0 \quad\quad\quad\quad 0 \\ &\to 0 &\text{ by SR }. \end{array}$$ These are two geometric progressions with the ratios: $r=1/5,\ -3/5$, that satisfy $|r| <0$. Meanwhile, our application of SR was justified by the fact that the two limits exit. $\square$

Exercise. Find the limit of the composition of $f(x)=\operatorname{sign}(x)$ and the sequence $x_n$ given by (a) $1/n$, (b) $-1/n$, (c) $(-1)^n/n$.

What is infinity?

The plus (or minus) infinity is identified with the collection of all sequences approaching this infinity. In other words, the following identity is read in both directions: $$\lim _{n\to +\infty}a_n=+\infty.$$

Now, does it make sense to do any algebra with the infinities? Yes, as long as the algebra with these limits makes sense.

The Algebraic Rules of Limits above have exceptions; we can imagine that one or both of the sequences approach infinity or that the limit in the denominator is $0$.

Theorem (Algebra of Infinite Limits of Sequences I). Suppose $a_n\to a$ and $b_n\to \pm\infty$. Then $$\begin{array}{|ll|llll|} \hline \text{SR: }& a_n + b_n\to \pm\infty& \text{CMR: }& c\cdot b_n\to \pm\infty& \text{ for any real }c>0\\ \text{PR: }& a_n \cdot b_n\to \operatorname{sign}(a)\infty& \text{QR: }& a_n/b_n\to 0, & b_n/a_n\to \pm\operatorname{sign}(a)\infty&\text{provided }a\ne 0 \\ \hline \end{array}$$

Theorem (Algebra of Infinite Limits of Sequences II). Suppose $a_n\to \pm\infty$ and $b_n\to \pm\infty$. Then $$\begin{array}{|ll|} \hline \text{SR: }& a_n + b_n\to \pm\infty& \\ \text{PR: }& a_n \cdot b_n\to +\infty& &\\ \hline \end{array}$$

Justified by these theorems, we follow the algebra of infinities: $$\begin{array}{|lll|} \hline \text{number } &+& (+\infty)&=+\infty\\ \text{number } &+& (-\infty)&=-\infty\\ +\infty &+& (+\infty)&=+\infty\\ -\infty &+& (-\infty)&=-\infty\\ \text{number } &/& (\pm\infty)&=0\\ \hline \end{array}$$ These are just shortcuts!

There is no $\infty -\infty$ (just as there is no $\infty /\infty$)... Why not?

Behind each $\infty$, there must be a sequence approaching $\infty$! However, the outcome is ambiguous; on the one hand we have: $$a_n=n \to+\infty,\ b_n=-n \to+\infty\ \Longrightarrow\ a_n- b_n=0 \to 0;$$ on the other: $$a_n=n^2 \to+\infty,\ b_n=-n \to+\infty\ \Longrightarrow\ a_n- b_n=n^2-n \to +\infty,$$ by Limits of Polynomials. Two seemingly legitimate answers for the same expression, $\infty -\infty$...

Infinity - infinity.png

We have another indeterminate expression!

7 More properties of limits of sequences

Only the tail of the sequence matters for convergence:

Only tail matters.png

Theorem (Convergence of Truncations). A sequence is convergent if and only if all of its truncations are convergent: $$\{a_n:\ n=p,p+1,...\}\to a \ \Longleftrightarrow\ \{a_n:\ n=p+1,p+2,...\}\to a.$$

Non-strict inequalities between sequences $$a\leftarrow a_n \ge b_n \to b, $$ are preserved under limits: $$a\ge b.$$

Comparison for sequences.png

Exercise. Show that replacing the non-strict inequality, $a_n \ge b_n$, with a strict one, $a_n > b_n$, won't produce a strict inequality in the conclusion of the theorem.

The situation is similar to that of the Uniqueness Theorem: if the opposite inequality were to hold, we could find two bands to contain the two sequences' tails so that the original inequality would fail:

Comparison for sequences -- bands.png

Theorem (Comparison Test). If $a_n \ge b_n$ for all $n$ greater than some $N$, then $$\lim_{n\to\infty} a_n \ge \lim_{n\to\infty} b_n, $$ provided the sequences converge.

Proof. The geometry of the proof is clear: we want to separate the two horizontal lines representing the two limits by two non-overlapping bands, as shown above. Then, if narrow enough, the tails of the “larger” sequence would have to fit the “smaller” band. These bands correspond to two intervals around those two limits. In order for them to be disjoint, their width (that's $2\varepsilon$!) should be less than half the distance between the two numbers.

Proof of comparison of limits of sequences.png

The proof is by contradiction. Suppose $a$ and $b$ are the limits of $a_n$ and $b_n$ respectively and suppose also $a< b$. Let $$\varepsilon = \frac{b-a}{2}.$$ Then, what we are going to use at the end is $$a+\varepsilon=b-\varepsilon.$$

Now, we rewrite the definition for $a$ as limit:

  • there exists a natural number $N$ such that, for every natural number $n > L$, we have

$$|a_n - a| < \varepsilon .$$ Now, we rewrite the definition for $b$ as limit:

  • there exists a natural number $K$ such that, for every natural number $n > M$, we have

$$|b_n - b| < \varepsilon .$$ In order to combine the two statements, we need them to be satisfied for the same values of $n$. Let $$N=\max\{ L,M\}.$$ Then,

  • for every number $n > N$, we have

$$|a_n - a| < \varepsilon ,\text{ or } a-\varepsilon<a_n<a+\varepsilon,$$

  • for every number $n > N$, we have

$$|b_n - b| < \varepsilon ,\text{ or } b-\varepsilon<b_n<b+\varepsilon.$$ Taking one from either of the two pairs of inequalities, we have: $$ a_n < a+\varepsilon=b-\varepsilon<b_n.$$ A contradiction. $\blacksquare$

Warning: from such an inequality, we can't conclude anything about the existence of the limit:

Comparison no limit sequences.png

Having two inequalities, on both sides, may work better.

Squeeze Theorem for sequences.png

It is called a squeeze. If we can squeeze the sequence under investigation between two familiar sequences, we might be able to say something about its limit. Some further requirements will be necessary.

Theorem (Squeeze Theorem). If a sequence is squeezed between two sequences with the same limit, its limit also exists and is equal to the that number; i.e., $$a_n \leq c_n \leq b_n \text{ for all } n > N,$$ and $$\lim_{n\to\infty} a_n = \lim_{n\to\infty} b_n = c,$$ then the sequence $c_n$ converges and $$\lim_{n\to\infty} c_n = c.$$

Proof. The geometry of the proof is shown below:

Proof of Squeeze Theorem for sequences.png

Suppose $\varepsilon>0$ is given. As we know, we have for all $n$ larger than some $N$: $$c-\varepsilon < a_n < c+\varepsilon \text{ and } c-\varepsilon < b_n < c+\varepsilon.$$ Then we have: $$c-\varepsilon < a_n \le c_n \le b_n < c+\varepsilon.$$ $\blacksquare$

Example. Sometimes the choice of the squeeze is obvious. Consider: $$c_n=\frac{(-1)^n}{n}.$$ Examining the sequence reveals the two bounds:

Squeeze for (-1)^n n.png

In other words, we have: $$-\frac{1}{n} \le \frac{(-1)^n}{n} \le \frac{1}{n} .$$ Now, since both $a_n=-\frac{1}{n}$ and $b_n=\frac{1}{n}$ go to $0$, by the Squeeze Theorem, so does $c_n=\frac{(-1)^n}{n}$. $\square$

Example. Let's find the limit, $$\lim_{n \to \infty }\frac{1}{n} \sin n.$$

It cannot be computed by PR because $$\lim_{n \to \infty }\sin n.$$ does not exist. Let's try a squeeze. This is what we know from trigonometry: $$-1 \le \sin n \le 1. $$ However, this squeeze proves nothing about the limit of our limit!

Let's try another squeeze: $$-\left| \frac{1}{n} \right| \le \frac{1}{n} \sin\frac{1}{n} \le \left| \frac{1}{n} \right| .$$ Now, since $\lim_{n \to \infty }(-\frac{1}{n}) =\lim_{n \to \infty }\frac{1}{n}=0$, by the Squeeze Theorem, we have: $$\lim_{n \to \infty }\frac{1}{n} \sin n=0.$$ $\square$

Exercise. Suppose $a_n$ and $b_n$ are convergent. Prove that $\max\{a_n,b_n\}$ and $\min\{a_n,b_n\}$ are also convergent. Hint: start with the case $\lim a_n>\lim b_n$.

The squeeze theorem is also known as the Two Policemen Theorem: if two policemen are escorting a prisoner (handcuffed) between them, and both officers go to the same(!) police station, then -- in spite of some freedom the handcuffs allow -- the prisoner will also end up in that station.

Two Policemen Theorem.png

Another name is the Sandwich Theorem. It is, once again, about control. A sandwich can be a messy affair: ham, cheese, lattice, etc. One won't want to touch that and instead takes control of the contents by keeping them between the two buns. He then brings the two to his mouth and the rest of the sandwich along with them!

Sandwich Theorem.png

To make conclusions about divergence to infinity, we only need to control it from one side.

Theorem (Squeeze Theorem for divergence). If $a_n \ge b_n$ for all $n$ greater than some $N$, then we have: $$\begin{array}{lll} \lim_{n\to\infty} a_n =-\infty&\Longrightarrow& \lim_{n\to\infty} b_n=-\infty;\\ \lim_{n\to\infty} a_n =+\infty&\Longleftarrow& \lim_{n\to\infty} b_n=+\infty. \end{array}$$

Exercise. Prove the theorem.

Exercise. Suppose a sequence is defined recursively by $$a_{n+1}=2a_n+1\text{ with } a_0=1.$$ Does the sequence converge or diverge?

8 Theorems of Introductory Analysis

The theorems in this section will be used to prove new theorems. It can be skipped on the first reading.

We accept the following fundamental result without proof.

Theorem (Monotone Convergence Theorem). If a sequence is bounded and monotonic, i.e., it is either increasing, $a_n\le a_{n+1}$ for all $n$, or decreasing, $a_n\ge a_{n+1}$ for all $n$, then it is convergent.

Rational sequence with limit.png

The result is also known as the Completeness Property of Real Numbers.

Theorem (Nested Intervals Theorem). (1) A sequence of nested closed intervals has a non-empty intersection, i.e., if we have two sequences of numbers $a_n$ and $b_n$ that satisfy $$a_1\le a_2\le ... \le a_n\le ... \le b_n\le ... \le b_2\le b_1,$$ then they both converge, $$a_n\to a,\ b_n\to b,$$ and $$\bigcap_{n=1}^\infty [a_n,b_n]=[a,b].$$ (2) If, moreover, $$b_n-a_n\to 0,$$ then $$\bigcap_{n=1}^\infty [a_n,b_n]=\{a\}=\{b\}.$$

Proof. For part (1), observe that a point $x$ belongs to the intersection if and only if it satisfies: $$a_n\le x \le b_m,\ \forall n,m.$$ Meanwhile, the sequences converge by the Monotone Convergence Theorem. Therefore, $$a\le x\le b$$ by the Comparison Theorem.

For part (2), consider: $$0=\lim _{n\to \infty} (b_n-a_n)=\lim _{n\to \infty} b_n-\lim _{n\to \infty} a_n=b-a,$$ by SR. We then conclude that $a=b$. $\blacksquare$

Nested intervals.png

We have indeed a “nested” sequence of intervals $$I=[a,b] \supset I_1=[a_1,b_1] \supset I_2=[a_2,b_2] \supset ...,$$ with a single point $A$ in common.

Definition. Given a set $S$ of real numbers, its upper bound is any number $M$ that satisfies: $$x\le M \text{ for any } x\text{ in } S.$$ Its lower bound is any number $m$ that satisfies: $$x\ge m \text{ for any } x\text{ in } S.$$

For $S=[0,1]$, any number $M\ge 1$ is its upper bound. However, these sets have no upper bounds: $$(-\infty,+\infty),\ [0,+\infty),\ \{0,1,2,3,...\}.$$

Definition. A set that has an upper bound is called bounded above and a set that has a lower bound is called bounded below. A set that has both upper and lower bounds is called bounded; otherwise it's unbounded.

Definition. For a set $S$, an upper bound for which there is no smaller upper bound is called a least upper bound; it is also called supremum and is denoted by $\sup S$. For a set $S$, a lower bound for which there is no larger upper bound is called a greatest lower bound; it is also called infimum and is denoted by $\inf S$.

Thus, $M=\sup S$ means that

  • 1. $M$ is an upper bound of $S$, and
  • 2. if $M'$ is another upper bound of $S$, then $M'\ge M$.

Now, if we have another $M'=\sup S$, then

  • 1. $M'$ is an upper bound of $S$, and
  • 2. if $M$ is another upper bound of $S$, then $M\ge M'$.

Therefore, $M=M'$.

Theorem. For a given set, there can be only one least upper bound.

Thus, we are justified to speak of the least upper bound.

Example. For the following sets the least upper bound is $M=3$:

  • $S=\{1,2,3\}$;
  • $S=[1,3]$;
  • $S=(1,3)$.

The proof for the last one is as follows. Suppose $M'$ is an upper bound with $1<M'<3$. Let's choose $a=\frac{3+M'}{2}$. But $a$ belongs to $S$! Therefore, $M'$ isn't an upper bound.

Sup(1,3)=3.png

What if we limit $S$ to the rational numbers only in $(1,3)$? Then $a=\frac{3+M'}{2}$ won't belong to $S$ when $M'$ is irrational. The proof fails. $\square$

Theorem (Existence of $\sup$). Any bounded above set has a least upper bound. Any bounded below set has a greatest lower bound.

Proof. The idea of the proof is to construct nested intervals with the right-end points being upper bounds. What should be the left-end points?

Lub exists.png

Given a set $S$, let

  • $U$ be the set of all upper bounds of $S$;
  • $L$ be the set of all lower bounds of $U$.

Since $S$ is bounded $$U\ne \emptyset.$$ Now, if $S$ is a single point, we are done. If not, we have $x,y$ in $S$ such that $x<y$. Therefore, $x$ belongs to $L$ and $$L\ne \emptyset.$$

We start with:

  • $a_1$ is any element of $L$ and $b_1$ is any element of $U$.

Suppose inductively that we have constructed two sequences of numbers $$a_i,\ b_i,\ i=1,2,3..., n,$$ such that:

  • 1. $a_i$ is in $L$ and $b_i$ is in $U$;
  • 2. $a_n\le...\le a_1\le b_1\le ...\le b_n$;
  • 3. $b_i-a_i\le \frac{1}{2^{i-1}}(b_1-a_1)$.
Lub exists 2.png

We continue with the inductive step: let $$c=\frac{1}{2}(b_n-a_n).$$ We have two cases.

Case 1: $c$ belongs to $U$. Then choose $$a_{n+1}=a_n \text{ and } b_{n+1}=c.$$ Then, $$a_{n+1}=a_n\in L,\ b_{n+1}=c\in U.$$ Case 2: $c$ belongs to $L$. Then choose $$a_{n+1}=c \text{ and } b_{n+1}=b_n.$$ Then, $$a_{n+1}=c\in L,\ b_{n+1}=b_n\in U.$$

Furthermore, $$b_{n+1}-a_{n+1}=\frac{1}{2}(b_n-a_n)\le \frac{1}{2}\frac{1}{2^{n-1}}(b_1-a_1)=\frac{1}{2^{n}}(b_1-a_1).$$ Thus, all the conditions are satisfied, and our sequence of nested intervals has been inductively built. We apply the Nested Intervals Theorem and conclude that $$a_n\to d\leftarrow b_n.$$

Why is $c$ a least upper bound of $S$?

Lub exists 3.png

First, suppose $c$ is not an upper bound. Then there is $x\in S$ with $x>c$. If we choose $\varepsilon =x-c$, then from $b_n \to c$ we conclude that $b_n<x$ for all $n>N$ for some $N$. This contradicts the assumption that $b_n\in U$.

Second, suppose $c$ is not a least upper bound. Then there is an upper bound $y<c$. If we choose $\varepsilon =c-y$, then from $a_n \to c$ we conclude that $a_n>y$ for all $n>N$ for some $N$. This contradicts the assumption that $a_n\in L$. $\blacksquare$

Theorem (Intermediate Point Theorem). A subset $J$ of the reals is an interval or a point if and only if it contains all of its intermediate points; i.e., $$J\ni y_1<c< y_2\in J \ \Longrightarrow\ c\in J.$$

Proof. The “if” part is obvious. Now assume that the condition is satisfied for set $J$. Suppose also that $J$ is bounded. Then these exist by the Existence of $\sup$ theorem: $$a=\inf S,\ b=\sup J.$$ Note that these might not belong to $J$. However, if $c$ satisfies $a\le c\le b$, then there are

  • $y_1\in J$ such that $a<y_1<c$, and
  • $y_2\in J$ such that $c<y_2<b$.

By the property, then we have: $c\in J$. Therefore, $J$ is an interval with $a,b$ its end-points. $\blacksquare$

Exercise. Prove the theorem for the unbounded case.

Theorem (Bolzano-Weierstrass Theorem). Every bounded sequence has a convergent subsequence.

Proof. Suppose $\{x_n\}$ is such a sequence. Then, it is contained in some interval $[a,b]$. The first part of the construction is to cut consecutive intervals is half and pick the half that contains infinitely many elements of $\{x_n\}$.

Similarly to the previous proofs, we assume that we have already constructed sequences: $$a_i,\ b_i,\ i=1,2,3..., n,$$ such that:

  • 1. $[a_i,b_i]$ contains infinitely many elements of $\{x_n\}$;
  • 2. $a_n\le...\le a_1\le b_1\le ...\le b_n$;
  • 3. $b_i-a_i\le \frac{1}{2^{i-1}}(b_1-a_1)$.

We continue with the inductive step: let $$c=\frac{1}{2}(b_n-a_n).$$ We have two cases.

Bolzano-Weierstrass Theorem.png

Case 1: interval $[a_n,c]$ contains infinitely many elements of $\{x_n\}$. Then choose $$a_{n+1}=a_n \text{ and } b_{n+1}=c.$$ Case 2: interval $[a_n,c]$ does not contain infinitely many elements of $\{x_n\}$, then $[c,b_n]$ does. Then choose $$a_{n+1}=c \text{ and } b_{n+1}=b_n.$$

As before, $$b_{n+1}-a_{n+1}=\frac{1}{2}(b_n-a_n)\le \frac{1}{2}\frac{1}{2^{n-1}}(b_1-a_1)=\frac{1}{2^{n}}(b_1-a_1).$$

The intervals are constructed as desired; the intervals are zooming in on the denser and denser parts of the sequence:

Bolzano-Weierstrass Theorem 2.png

Now we apply the Nested Intervals Theorem to conclude that $$a_n\to d\leftarrow b_n.$$

The second part of the construction is to choose the elements of the subsequence $\{y_k\}$ of $\{x_n\}$, as follows. We just pick as $y_{k}$ any element of $\{x_n\}$ in $[a_k,b_k]$ that comes later in the sequence than the ones already added, i.e., $y_1,y_2,...,y_{k-1}$. This is always possible because we always have infinitely many elements left to choose from. Once the subsequence $\{y_k\}$ is constructed, we have $y_k\to d$ by the Squeeze Theorem. $\blacksquare$

9 Compositions

What about compositions?

Since the input of a sequence -- as a function -- is an integer but the output could be any number, there is no such thing as the composition of two sequences (unless the first one is integer-valued): $$\newcommand{\ra}[1]{\!\!\!\!\!\xrightarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} % \begin{array}{ccccccccccccccc} \text{integer input}, n & \mapsto & \begin{array}{|c|}\hline\text{ sequence } \\ \hline\end{array} & \mapsto & \text{real output}, a_n\\ &&&&\text{integer input}, m & \mapsto & \begin{array}{|c|}\hline\text{ sequence } \\ \hline\end{array} & \mapsto & \text{real output}, b_m \end{array}$$ If the second one is just a function of real variable, there is no problem: $$\newcommand{\ra}[1]{\!\!\!\!\!\xrightarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} % \begin{array}{ccccccccccccccc} \text{integer input}, n & \mapsto & \begin{array}{|c|}\hline\text{ sequence } \\ \hline\end{array} & \mapsto & \text{real output}, a_n\\ &&&&\text{real input}, x & \mapsto & \begin{array}{|c|}\hline\text{ function } \\ \hline\end{array} & \mapsto & \text{real output}, y \end{array}$$ So, for a function $f$ defined on an interval, a sequence $$y_n=f(a_n)$$ is likely to make sense.

What about the limit of the new sequence? Can we say, similar to the four rules of limits, the limit of composition is the composition of the limits? Well, there is no such thing as composition of numbers...

Let's look at some examples.

Example. Sometimes the algebra is obvious. If $f$ is a linear polynomial, $$f(x)=mx+b,$$ and we have a sequence $x_n\to a$, we can use the Sum Rule and the Constant Multiple Rule to prove the following: $$\begin{array}{lll} \lim_{n\to \infty} f( x_n ) &=\lim_{n\to \infty} (m x_n +b) \\ &=m\lim_{n\to \infty} x_n +b\\ &=ma+b \\ &=f(a). \end{array}$$ $\square$

What we see is that the limit of the composition is the value of the function at the limit!

Example. Let's try $f(x)=x^2$ and a sequence that converges to $0$.

Limit of x^2.png

Bottom: how $x$ depends on $n$, middle: how $y$ depends on $x$, right: how $y$ depends on $n$. Can we prove what we see? An application of the Product Rule in this simple situation reveals: $$\begin{array}{lll} \lim_{n\to \infty} \big( x_n \big)^2 &=\lim_{n\to \infty} \left( x_n\cdot x_n \right)\\ &=\lim_{n\to \infty} x_n\cdot \lim_{n\to \infty}x_n \\ &=\left(\lim_{n\to \infty} x_n\right)^2, \end{array}$$ provided that limit exists. $\square$

A repeated use of PR produces a more general formula: if sequence $x_n$ converges then so does $(x_n)^p$ for any positive integer $p$, and $$\lim_{n\to\infty} \left[ (x_n)^p \right] = \left[ \lim_{n\to\infty} x_n \right]^p.$$ Combined with the Sum Rule and the Constant Multiple Rule this proves the following.

Theorem (Composition Rule for Polynomials). If sequence $x_n$ converges then so does $f(x_n)$ for any polynomial $f$, and $$\lim_{n\to\infty} f(x_n) = f\left[ \lim_{n\to\infty} x_n \right].$$

Then, we conclude that limits behave well with respect to composition with some functions. In general, new sequences are produces via compositions with functions: given a sequence $x_n$ and a function $y=f(x)$, define $$y_n=f(x_n).$$

New sequences as compositions.png

But what about other functions: $$f(x)=\sqrt{x},\ g(x)=\sin x,\ h(x)=e^x?$$

Example. This time we choose a sequence that approaches $0$ from both sides: $$x_n=(-1)^n\frac{1}{n^.8} \text{ and } f(x)=-\sin 5x.$$

Limit of function as composition.png

We see the same pattern! $\square$

Example. What if we choose $$x_n=\frac{1}{n} \text{ and } f(x)=\frac{1}{x}?$$ Then, obviously, we have $$y_n=\frac{1}{1/n}=n\to\infty!$$

Limit of 1x with sequence.png

$\square$

In the next chapter, we will use this construction to study the limits of functions rather than those of sequences. A few examples of that are presented in the next section.

10 Famous limits

The graph of $y=\sin x$ almost merges with the line $y=x$ around $0$. Moreover, plotting the points $(1/n,\sin 1/n)$ reveals a straight line with slope $1$:

Y=sinx and y=x.png

Let's compare the two algebraically.

Theorem. $$\lim_{n\to \infty} \frac{\sin x_n}{x_n} =1,$$ for any sequence $x_n\to 0$.

Proof. The conclusion follows from the trigonometry fact: $$ \cos x < \frac{\sin x}{x} < 1, $$ and the Squeeze Theorem. $\blacksquare$

The graph of $y=\cos x$ almost merges with the line $y=1$ when close to the $y$-axis. Moreover, plotting the points $(1/n,1-\cos 1/n)$ shows that the slope converges to $0$:

Y=cosx and y=1.png

Let's compare the two algebraically.

Theorem. $$\lim_{n\to \infty} \frac{1 - \cos x_n}{x_n} = 0,$$ for any sequence $x_n\to 0$.

Exercise. Prove the theorem.

From these results and QR, we acquire the following.

Corollary. $$\lim_{n\to \infty} \frac{\tan x_n}{x_n} =1,$$ for any sequence $x_n\to 0$.

Y=tanx and y=x.png

Note that these results suggest a way of understanding the limit of a function at a point discussed in the next chapter.

The ancient Greeks' way of understanding and computing the length of a circle of radius $r$ was to approximate the circle with regular polygons. Let's carry out this construction for circumscribing polygons:

Circle approximations.png

Theorem. The limit of the perimeters of regular polygons circumscribing a circle of radius $r$ is $2\pi r$.

Proof. We split each such polygon with $n$ sides into $2n$ right triangles and compute their dimensions:

Circle approximations 2.png

Each of them has this angle at the center: $$\alpha_n=\frac{2\pi}{2n}=\frac{\pi}{n}$$ Therefore, the length of the opposite side is $$h_n=r\tan \frac{\pi}{n}.$$ The perimeter of the whole polygon is $$\begin{array}{lll} P_n&=h_n\cdot 2n\\ &=r\tan \frac{\pi}{n}\cdot 2n \\ &=2r\pi\cdot\frac{\tan \frac{\pi}{n}}{\frac{\pi}{n}}\\ &\to 2\pi r \quad \text{ as }n\to\infty, \end{array}$$ according to the last corollary. $\blacksquare$

Exercise. Carry out this construction for inscribed polygons.

Example (compounded interest). Suppose we have money in the bank at APR $10\%$ compounded annually. Then after a year, given $\$ 1,000$ initial deposit, you have $$\begin{aligned} 1000 + 1000\cdot 0.10 &= 1000(1 + 0.1) \\ &= 1000 \cdot 1.1. \end{aligned}$$ Same every year. After $t$ years, it's $1000\cdot1.1^{t}$. What if it is compounded semi-annually, with the same APR? After $\frac{1}{2}$ year, $1000\cdot 0.05$, or total $$ 1000 + 1000\cdot 0.05 = 1000\cdot 1.05;$$ after another $\frac{1}{2}$ year, $$\left(1000\cdot 1.05\right)\cdot 1.05 = 1000 \cdot 1.05^{2}. $$ After $t$ years, $$ 1000\cdot (1.05^{2})^{t} = 1000\cdot 1.05^{2t}. $$ Note that we are getting more money: $1.05^{2} = 1.1025 > 1.1$!

Try compound quarterly, $$ 1000\cdot 1.025^{4t}. $$ If compounded $n$ times, then $$ 1000 \cdot \left(1 + \frac{1}{n}\right)^{nt}, $$ where $\frac{1}{n}$ is the interest in one period.

Interest compunded more and more.png

Generally, for APR $r$ (given as a decimal) and for the initial deposit $A_{0}$, after $t$ years, the current amount is $$A(t) = A_{0}\left(1 + \frac{r}{n} \right)^{nt},$$ if compounded $n$ times per year.

What if we compounded more and more, will we be paid unlimited amounts? No. $\square$

Limit e=(1+1n)^n.png

Theorem (e). The limit below exists: $$\lim_{n\to \infty} \left( 1+\frac{1}{n} \right)^n .$$

Proof. First, we show that the sequence $$a_n=\left(1+\frac{1}{n}\right)^{n},$$ is increasing. We have: $$\begin{array}{lll} \dfrac{a_{n+1}}{a_n}&=\dfrac{\left(1+\tfrac{1}{n+1}\right)^{n+1}}{\left(1+\tfrac{1}{n}\right)^n}=\dfrac{\left(\frac{n+2}{n+1}\right)^{n+1}}{\left(\frac{n+1}{n}\right)^n}\\ &=\left(\dfrac{n+2}{n+1}\right)^{n+1}\left(\dfrac{n}{n+1}\right)^{n+1}\left(\dfrac{n+1}{n}\right)^1\\ &=\left(\dfrac{n^2+2n+1-1}{n^2+2n+1}\right)^{n+1}\dfrac{n+1}{n}\\ &=\left(1-\dfrac{1}{(n+1)^2}\right)^{n+1}\dfrac{n+1}{n}. \end{array}$$ We use the Bernoulli Inequality: $$(1+a)^m > 1+ma,$$ for any $a$. We just choose $a=\tfrac{-1}{(n+1)^2}$ and $m=n+1$. Then $$\begin{array}{lll} \dfrac{a_{n+1}}{a_n} & > \left(1-\dfrac{1}{n+1}\right)\dfrac{n+1}{n}\\ &=\dfrac{n}{n+1}\dfrac{n+1}{n}\\ &=1. \end{array}$$ In a similar fashion we show that the sequence $$b_n=\left(1+\frac{1}{n}\right)^{n+1},$$ is decreasing. Since $a_n<b_n$, we conclude that former sequence is both increasing and bounded. Therefore, it converges by the Monotone Convergence Theorem. $\blacksquare$

Notation: We denote this limit by $e$: $$e=\lim_{n\to \infty} \left( 1+\frac{1}{n} \right)^n .$$ It is also known as the “Euler number”.

Example. We continue... What if the interest is compounded $n$ times and $n \to \infty$? Then we have: $$ \begin{aligned} \lim_{n \to \infty} A(t) & = \lim_{n \to \infty} A_{0} \left( 1 + \frac{r}{n} \right)^{nt} \\ &= A_{0} \lim_{n \to \infty} \left( 1 + \frac{r}{n} \right)^{nt} \text{ ... by CMR} \\ & = A_{0} \left( \lim_{n \to \infty} \left(1 + \frac{r}{n}\right)^{n}\right)^{t} \\ & = A_{0} (e^{r})^{t}. \end{aligned}$$ Thus, with APR of $r$ and an initial deposit $A_{0}$, after $t$ years you have: $$A(t) = A_{0} e^{rt}. $$ We say that the interest is compounded continuously.

Suppose APR is $10\%$, $A_{0} = 1000$, $t = 1$. Then, $$A(1)=1000\cdot e^{1.1} = 1000\cdot e^{0.1} \approx \$1,105, $$ interest $ \$1,105 > \$100 $ (annual).

How long does it take to triple your money with APR=$5\%$, compounded continuously? Set $A_{0} = 1$ and solve for $t$: $$\begin{array}{rll} 3 & =& 1\cdot e^{0.05t} &\Longrightarrow\\ \ln 3 &=& 0.05t &\Longrightarrow\\ t &=& \frac{\ln 3}{0.05} &= 22 \text{ years.} \end{array}$$ $\square$

Exercise. Give formulas for the following sequences: (a) $a_n\to 0$ as $n\to \infty$ but it's not increasing or decreasing; (b) $b_n\to +\infty$ as $n\to \infty$ but it's not increasing.

11 Transcendental functions

We consider the exponential function and the logarithm and justify treating these functions as defined on $(-\infty,\infty)$.

We first defined the exponential function $f(x)=a^x,\ a>0$ for all integer values of $x$ as repeated multiplication (or division in case of a negative $x$):

Exponential function from points 2.png

We then extended the definition to all rational numbers $x=\frac{p}{q}$ by means of the formula: $$a^{\frac{p}{q}}=\sqrt[q]{a^p}=\left( \sqrt[q]{a}\right)^p.$$

Exponential function from points 3.png

Now, what about $a^x$ for real values of $x$?

Definition. The natural exponential function, or the exponential function base $e$, is defined by its values for each real $x$: $$e^x=\lim_{n\to \infty}\left( 1+\frac{x}{n} \right)^n.$$

Theorem. The exponential function is well-defined.

Proof. Following the proof in the last section, we demonstrate that this limit exists. $\blacksquare$

As we know from the last chapter, this function is increasing for all rational $x$. Then, from the comparison theorem, we conclude that it is also increasing on $(-\infty,\infty )$. Therefore, it is one-to-one.

Definition. The natural logarithm function, or the logarithm function base $e$, is defined as the inverse of the natural exponential function.

Definition. The exponential function base $b>0$ is defined by its values for each real $x$: $$b^x=e^{x\ln b}.$$

The definition matches the old one given for the rational $x$.

Definition. The logarithm function base $b>0$ is defined as the inverse of the exponential function base $b$.