Asymptotic comparison – I

In the coming posts, I want to discuss the notions of asymptotic comparison, which is essentially the mathy way of saying “these two things look alike” or “this one is much larger than this other one”. The point, as with many new notions, is to simplify. Most of the expressions / formulas / functions that we encounter in real life are often extremely cumbersome and too complicated to deal with directly. This might not be obvious from a typical undergrad math course, because often, well, things just work: derivatives are easy to compute, everything factorizes nicely, integrals are explicit, Gaussian elimination involves no fractions, and eigenvalues are all integers. It is sadly a myth; more often than not, direct or explicit computations are not possible, and it is necessary to understand and simplify before getting into the thick of things. What does this mean? Well, this depends on what you are trying to achieve. Asymptotic comparison is about studying the behavior of a sequence when n is “large”, or of a function “close to” some point x_0.

In my long rant about L’Hospital rule, I said that “\sin x looks like x when x is small”, and that “x wins over \ln x when x is large”. What does this really mean? I will keep this for another time, and focus the first posts about asymptotic comparison on sequences, since as usual, most notions are easier to grasp with sequences. We will seek to compare two sequences when n is large. For now, it will mostly help to compute limits, but I hope to make apparent in other posts how such arguments can drastically facilitate a bunch of calculus concepts, while becoming very much necessary for more advanced topics.

This post is specifically about equivalents, a.k.a. the clear notion of “looking alike”. Let us look at three sequences u_n = 5n, v_n = n^2, and w_n = n^2 + 3n. As often for sequences, we only care about what happens when n is large (whatever that means). If we take n = 1000, we get

\displaystyle u_n = 5,000, \quad v_n = 1,000,000, \quad w_n = 1,003,000,

while for $n = 50,000$, we obtain

\displaystyle u_n = 250,000, \quad v_n = 2,500,000,000, \quad w_n = 2,500,150,000.

Clearly, all these numbers are large, and we can make them as large as we want by taking n large enough: this is just saying that

\displaystyle \lim_{n \to + \infty} u_n = \lim_{n \to + \infty} v_n  = \lim_{n \to + \infty} w_n = + \infty.

However, v_n and w_n are clearly much larger than u_n. On the other hand, v_n and w_n are quite similar. Think of money: you would much rather have 2.5 billion bucks than 250 thousand, but if you have 2.5 billion, 150 thousand more in the bank will not make much of a difference for you.

The point is: everything is relative. A quantity is never small or large by itself, but it can be much larger or much smaller than another quantity (measured in the same unit). On the same note, two quantities are similar if they differ by something small… compared to one of them. This will justify the following definitions.

Formal definition

In all the following, to simplify, we assume that all sequences never take the value zero (at least for n large enough). For all intents and purposes, it is not an issue.

Consider two sequences (u_n) and (v_n). We say that (u_n) and (v_n) are equivalent if

\displaystyle \lim_{n \to +\infty} \frac{u_n}{v_n} = 1.

We then write u_n \sim v_n.

The symbol \sim is one of what is collectively known as the Landau notation. I will cover the other ones in other posts. In \LaTeX, this symbol is given by \sim.

This definition does not seem to be exactly what we hinted at before, but this is indeed the same, as can be easily checked.

Show that (u_n) and (v_n) are equivalent if and only the difference between them is small compared to either of them. In symbols, check that u_n \sim v_n if and only if

\displaystyle \lim_{n \to +\infty} \frac{u_n-v_n}{u_n} = 0

and if and only if

\displaystyle \lim_{n \to +\infty} \frac{u_n-v_n}{v_n} = 0.

Remember that “if and only if” means that both implications are true: if u_n \sim v_n, then (u_n-v_n)/u_n \to 1, and if (u_n-v_n)/u_n \to 1 , then u_n \sim v_n.

Both of these could be taken as a definition, and both are good to remember. In practice, it is however usually easier and more useful to use the fact that u_n/v_n \to 1.

From the earlier discussion, we should have that n^2 + 3 n \sim n^2, and this is easy to check, since

\displaystyle \frac{n^2+3n}{n^2} = 1 + \frac{3}{n} \to 1 + 0 = 1.

More generally, assume that u_n is a sum of powers of n. Then (u_n) is equivalent to its term of highest degree. In formulas, if

\displaystyle u_n = c n^{\alpha} + c_1 n^{\alpha_1} + c_2 n^{\alpha_2} + \cdots + c_k n^{\alpha_k}

with c \neq 0 and \alpha_1, \dots, \alpha_k < \alpha, then u_n \sim c n^{\alpha}.

Properties

Computation

If we call two things are “equivalent”, we often mean that they are “essentially the same”, so it would be a really poor choice of vocabulary if we did not have a few basic properties.

Take three sequences (u_n), (v_n), (w_n). Then we have the following properties.

  1. (Reflexivity) We have u_n \sim u_n.
  2. (Symmetry) If u_n \sim v_n, then v_n \sim u_n.
  3. (Transitivity) If u_n \sim v_n and v_n \sim w_n, then u_n \sim w_n.

This is merely a sanity check which is quite easy to verify.

Prove Proposition II.1.

However, one of the easy but very exciting properties of equivalents is that equivalents can be multiplied and exponentiated to any power, in the following sense.

Take sequences (u_n), (v_n), (x_n), (y_n). Then we have the following properties.

  1. If u_n \sim x_n and v_n \sim y_n, then u_n v_n \sim x_n y_n.
  2. If u_n \sim x_n, then for any \alpha \in \mathbb{R}, we have u_n^{\alpha} \sim x_n^{\alpha}.
  3. In particular, if u_n \sim x_n and v_n \sim y_n, then 1/u_n \sim 1/x_n and u_n / v_n \sim x_n / y_n.

Let us check the first one. Assume that that u_n \sim x_n and v_n \sim y_n. Then we want to compute the limit of (u_n v_n)/(x_n y_n). But we have

\displaystyle \frac{u_n v_n}{x_n y_n} = \frac{u_n}{x_n} \times \frac{v_n}{y_n} \to 1 \times 1 = 1,

since u_n \sim x_n and v_n \sim y_n , which means u_n / x_n \to 1 and v_n / y_n \to 1.

Check the other properties.

All this allows to simply compute a bunch of equivalents. From Exercise I.2 and Proposition II.2, we can get

\displaystyle \frac{3 n^4 + 5n +6}{7n^5 + 3n^4 - 2n} \sim \frac{3 n^4}{7n^5} = \frac{3}{7n}

or

\displaystyle \sqrt{n^4+5n + 1} \ln n \sim \sqrt{n^4} \ln n = n^2 \ln n.

Bottom line: we transform a complicated expression into a very simple one.

Equivalents and limits

One important property of equivalents is that they preserve limits: two equivalent expressions have the same limit.

Let (u_n), (v_n) be two sequences and \ell \in \mathbb{R} \cup \{\pm \infty\}.

  1. If u_n \sim v_n and v_n \to \ell, then u_n \to \ell.
  2. If u_n \to \ell and \ell is a non-zero finite number, then u_n \to \ell.

As before, this is proved by simple operations on limits. In the first case,

\displaystyle u_n = \frac{u_n}{v_n} \times v_n \to 1 \times \ell = \ell,

while in the second case

\displaystyle \frac{u_n}{\ell} \to \frac{\ell}{\ell} = 1.

Note that we need \ell \neq 0.

Show that if u_n \sim v_n and v_n has no limit, then u_n has no limit.

This gives simple ways to compute limits, without much effort.

Let us take a look at

\displaystyle u_n = \frac{\sqrt{9n^2+3n-5}}{(8n^3-3n+1/n)^{1/3}}.

We first have 9n^2+3n-5 \sim 9n^2 and 8n^3 + 3n + 1/n \sim 8n^3 by Exercise I.2. Then Proposition II.2 gives \sqrt{9n^2+3n-5} \sim \sqrt{9n^2} = 3n and (8n^3 + 3n + 1/n)^{1/3} \sim (8n^3)^{1/3} = 2 n, and then

\displaystyle u_n \sim \frac{3n}{2n} = \frac32,

which means, by Proposition II.3, that

\displaystyle \lim_{n \to +\infty} u_n = \frac32.

With a bit of habit, this takes one line, and no effort at all!

One thing seems innocuous in Proposition II.3, but is very much not. This result essentially tells that the equivalent is the limit. But it only works for limits which are neither zero nor \pm \infty. So having a limit 1, 2, -1, \pi is the same as being equivalent to 1, 2, -1, \pi. On the other hand, there are different ways to tend to zero. The sequences u_n = 1/n and v_n = 2^{-n} both tend to zero, but (v_n) converges much faster: we have u_{100} = 10^{-2} but v_{100} \approx 10^{-30}. Informally, two sequences tending to zero are equivalent if they tend to zero at the same speed. Similarly, two sequences tending to + \infty are equivalent if they tend to + \infty at the same speed. This is not true for finite non-zero limits. The two sequences x_n = 1+1/n and y_n = 1+2^{-n} are equivalent, since they both converge to the non-zero finite number 1. However, (y_n) goes to 1 much faster than (x_n). The speed of convergence should really be measured by how fast (x_n - 1) and (y_n - 1) go to 0, and indeed, these two latter sequences (which are the (u_n) and (v_n) from before) are very much not equivalent.

Sort the following sequences in different groups of equivalent sequences.

\displaystyle a_n = 1+1/n, \quad b_n = 2^n, \quad c_n = 2n^2+3n+5/n, \quad d_n = 2^{n+1},

e_n = \frac{1}{n+1}, \quad f_n = \frac{4n^3-5n+2}{2n+5/n}, \quad g_n = \frac{\sqrt{4n^6+2n}}{(n^3+5)^{1/3}}, \quad h_n = \frac{n+4}{\sqrt{n^2+2}}.

Geometric sequences

Exercise I.2 provides a neat way to find an equivalent of a sum of powers of n: we keep the term with the largest power. Similarly, it is easy to find an equivalent of a sum of geometric sequences: we keep the term with the largest common ratio. For instance, take u_n = 3^n + 2^n and v_n = 3^n. Then

\displaystyle \frac{u_n}{v_n} = \frac{3^n + 2^n }{3^n} = 1 + \frac{2^n}{3^n} = 1 + (2/3)^n \to 1 + 0 = 1,

since 0 < 2/3 < 1 and thus (2/3)^n \to 0. This means u_n \sim v_n.

More generally, assume that u_n is a sum of geometric sequences. Then (u_n) is equivalent to the term with the largest common ratio (in absolute value). In formulas, if

\displaystyle u_n = c r^n + c_1 r_1^n + c_2 r_2^n + \cdots + c_k r_k^n

with c \neq 0 and |r_1|, \dots, |r_k| < |r|, then u_n \sim c r^n.

This allows us to do computations such as

\displaystyle \frac{4^n+3^n+2^n}{3^n+2^n} \sim \frac{4^n}{3^n} = (4/3)^n,

and therefore this sequence tends to + \infty. Even more: it tends to + \infty at the same speed as (4/3)^n, a.k.a. super fast.

Functions of equivalents: the nice case

For now, we only know how to get equivalents for simple expressions involving powers or geometric sequences. What happens if we wish to get an equivalent of an expression involving a logarithm, an exponential, or others? In some cases, it is actually quite easy with a bit of calculus. Remember the meaning of the derivative: essentially, if we look close enough, a nice function looks like a straight line whose slope is given by the derivative. Informally, this reads, when x is close to x_0,

\displaystyle f(x) - f(x_0) \approx (x - x_0) f'(x_0).

For instance, this would give, if x is small,

\displaystyle e^x - 1 \approx x.

Replacing x by a sequence converging to 0 exactly yields the following result.

Assume that f is differentiable at x_0 \in \mathbb{R} with f'(x_0) \neq 0, and that (u_n) is a sequence converging to x_0. Then we have the equivalent

\displaystyle f(u_n) - f(x_0) \sim (u_n-x_0) f'(x_0).

Note how the right-hand side of f(u_n) - f(x_0) \sim (u_n-x_0) f'(x_0) is much simpler than u_n. The proof of this is essentially the definition of the derivative.

Show Theorem II.4.

In most of the cases, we will have x_0 = 0, and f is a usual function, from which we can deduce the following.

If u_n \to 0, then we have the following equivalents.

  • e^{u_n} - 1 \sim u_n.
  • \log(1+u_n) \sim u_n.
  • \sin(u_n) \sim u_n.
  • For any \alpha \in \mathbb{R}, (1+u_n)^{\alpha} - 1 \sim \alpha \: u_n.

Let us try this on an all-time favorite. In my experience, the computation of this limit unfortunately often turns into a math freak show.

Let us compute, for a fixed \lambda \in \mathbb{R},

\displaystyle \lim_{n \to + \infty} \left ( 1 + \frac{\lambda}{n} \right )^n.

It is of the form 1^{\infty} so it is very much an indeterminate form. For these, we take the log and get n \ln(1+\lambda/n). But \lambda/n \to 0, so from the previous result \ln(1+\lambda/n) \sim \lambda/n, and thus

\displaystyle n \ln \left( 1 + \frac{\lambda}{n} \right ) \sim n \frac{\lambda}{n} = \lambda,

which means

\displaystyle \lim_{n \to + \infty} n \ln \left( 1 + \frac{\lambda}{n} \right ) = \lambda.

Let us not forget that we took the log, so we need to exponentiate to get the limit, and finally obtain

\displaystyle \lim_{n \to + \infty} \left ( 1 + \frac{\lambda}{n} \right )^n = e^{\lambda}.

Again, the amount of computation and effort done is pretty much zero.

Equivalents and logarithms

In the previous result, we rely enormously on the fact that the sequence (u_n) is convergent to x_0 \in \mathbb{R}, and thus, f(u_n) is well-approximated by f(x_0) + (u_n-x_0)f'(x_0). If, for instance, u_n \to + \infty, then we do not have such tools at our disposal. There is a less important property of equivalents, which can however turn out to be quite useful and simplify things tremendously.

Assume that (u_n) and (v_n) are two strictly positive sequences with u_n \sim v_n and

\displaystyle \lim_{n \to + \infty} v_n = + \infty.

Then \ln u_n \sim \ln v_n.

In words, we can take the logarithm of equivalents, provided they tend to + \infty.

To see this, use properties of the logarithm to write

\displaystyle \frac{\ln u_n}{\ln v_n} =  \frac{\ln (u_n/v_n) + \ln v_n}{\ln v_n} =   \frac{\ln (u_n/v_n)}{\ln v_n} + 1.

But u_n/v_n \to 1 (since u_n \sim v_n), so \ln(u_n/v_n) \to \ln 1 = 0. Moreover v_n \to + \infty, so the last limit is of the type 0/\infty, and is therefore 0 (it would be very unwise to try to use L’Hospital rule!). We conclude that \ln(u_n)/\ln(v_n) \to 0 + 1 = 1, which is exactly what we wanted.

Consider

\displaystyle u_n = \frac{\ln(3^n+2^n)}{n}.

By Exercise 7, we have 3^n + 2^n \sim 3^n. But 3^n \to + \infty, so Proposition 4 gives \ln(3^n+2^n) \sim \ln(3^n) = n \ln 3. Therefore

\displaystyle u_n \sim \frac{n \ln 3}{n} = \ln 3,

which means

\displaystyle \lim_{n \to +\infty} u_n = \ln 3.

Of course, this is doable with L’Hospital, but I what would be the success rate? What if the denominator were replaced by \sqrt{\ln(e^{n^2} + \cos^2(2^{n^3}))}?

The assumptions that v_n \to + \infty is very important. Otherwise, it probably does not work, as the following example shows.

Consider u_n = 1 + 1/n and v_n = 1 + 1/n^2. Show that u_n \sim v_n but \ln(u_n) and \ln(v_n) are not equivalent.

Some words of caution

Equivalents and sum

The main point of equivalents is to say that some complicated sequence looks like a much more simple one, typically a power sequence c n^{\alpha} or a geometric sequences c r^n, maybe something with a logarithm c (\ln n)^{\alpha}, and, if you are feeling frisky, a product of all these c (\ln n)^{\alpha} n^{\beta} r^n. And there is not really a choice: a sequence cannot be equivalent to two different sequences of the above type!

What does this last statement really mean? Write it as a precise mathematical result, then prove it. You may need to use comparative growth: see the post on L’Hospital rule, and the next post on asymptotic comparison.

You may also have noticed that most of the previous results turn a big sum into just one term: in some sense, we only keep the one that wins over the other ones. This is for a very good reason: writing a sum in an equivalent is useless (on its right-side, which should be the “simple” expression).

Careful. Do not write sums in equivalents.

Think back to the first example given. Having 5,000$ is pretty neat. Having 1,000,000 is better. But having 1,003,000 or 1,008,000 or 999,873 is well, pretty much the same. In math, all sequences u_n = n^2, v_n = n^2 + 3n, w_n = n^2 + 8n, x_n = n^2 - 4 \sqrt{n} are equivalent. The n^2 in all these formulas wins, and what is written afterwards is essentially irrelevant. Yet, all these “rests” are very much not the same. But in comparison to the dominant term n^2, they are all ridiculously small. Therefore, if we let z_n = n^4 + 3n^3-5n+2, it is true that

\displaystyle z_n \sim n^4 + 3n^3,

but it is just as true that

\displaystyle z_n \sim n^4 + 500n^3,

or

\displaystyle z_n \sim n^4 + 3n^3+100n^2-47 n + 33 \ln^{10} n - 7/n^{2/3},

but the only relevant thing to write is

\displaystyle z_n \sim n^4.

Anything that we could write after the n^4 is totally insignificant. If you have more or less 1 million in the bank, and someone gives you (or steals from you) a couple thousand bucks, well, you still have more or less one million in the bank.

Equivalents and sum, again

The previous discussion should make clear the following point.

Careful. Equivalents cannot be summed.

In other words, if u_n \sim x_n and v_n \sim y_n, then it is in general wrong that u_n + v_n \sim x_n + y_n.

For instance, resuming the previous discussion, let u_n = n^3 + 10n and v_n = n^3 + n. It is true that u_n \sim n^3 and v_n \sim n^3, but u_n - v_n = 9n is very much not equivalent to 0. In our definition, it does not even make any sense! To be more convincing, it is also true that u_n \sim n^3 + n^2 yet u_n - v_n = 9n is very much not equivalent to n^3 + n^2 - n^3 = n^2.

You may notice that this happens because the largest term, which is the only relevant one, gets cancelled out. In some sense, it is possible to sum equivalents if they do not cancel out, but it is a slippery slope that is better not trodden.

Functions of equivalents: the bad case

Consider the sequences u_n = n^2 + n and v_n = n^2. As we saw u_n \sim v_n. However the two sequences e^{u_n} and e^{v_n} are not equivalent, since

\displaystyle \frac{e^{u_n}}{e^{v_n}} = e^{u_n - v_n} = e^n,

and this does not converge to 1. Another example of this phenomenon is in Exercise 9. A particularly terrible version of this is on limits of a sequence of the type u_n^{v_n}, where u_n \to 1 and v_n \to + \infty. This justifies the following rule.

Careful. We cannot take functions of equivalents.

In other words, if u_n \sim v_n and f is some function, then it is in general wrong that f(u_n) \sim f(v_n).

We saw two cases when we know what to do. One is that it is possible to take the log when the sequences tend to + \infty. Essentially, this is due to the fact that the log grows so slowly that differences are erased, whereas the exponential in the first example of this section exacerbates differences.

The other case is Theorem 4. As a reminder: if f is differentiable at x_0 \in \mathbb{R} with f'(x_0) \neq 0, and that (u_n) is a sequence converging to x_0, then

\displaystyle f(u_n) - f(x_0) \sim (u_n-x_0) f'(x_0).

Note how there are quite a few assumptions here, the most important being

  • the derivative of f at this point must not be 0;
  • the sequence needs to converge to a real number x_0.

The first point says, for instance, that we cannot so easily get a nice equivalent for a sequence like \cos(1/n). This is when the whole might of Taylor’s formulas is needed. This shall be covered in another post. The second point, on the other hand, has no really universal solution. Derivatives at + \infty are not really a thing (though one may try to use the mean value theorem), and it is often better done on a case by case basis.

Note also that, if x_0 \neq 0, then we have u_n \sim x_0. Moreover, f(u_n) - f(x_0) \sim (u_n-x_0) f'(x_0) and

\displaystyle \lim_{n \to + \infty} (u_n-x_0) f'(x_0) = (x_0 - x_0) f'(x_0) = 0,

so

\displaystyle \lim_{n \to + \infty} f(u_n) = f(x_0),

and thus, if f(x_0) \neq 0, then f(u_n) \sim f(x_0). In this sense, we did indeed take a function of an equivalent. However, this is really an extraneous consideration.

Do we really need this whole machinery to obtain the limit / equivalent of f(u_n)? What are we merely saying? What minimal reasonable assumption do we need to make on f to get this limit?

Theorem 4 is much more precise: it states that not only f(u_n) tends to f(x_0), but also the speed of convergence. As we discussed before, this means getting an equivalent of f(u_n) - f(x_0).

Extra exercises

Find the limit of the following sequences, as well as a simple equivalent if the limit is 0 or + \infty.

\displaystyle \frac{1}{n \sqrt{n+1}}, \quad \frac{n+1}{\sqrt{n^2+2n}}, \quad \frac{n \ln^2 n}{(n^2+1)^{1/3}}, \quad \frac{2^n + 3^n}{4^n+5^n},

\displaystyle \frac{n}{3^n \sqrt{n^2+2}}, \quad \frac{\sqrt{n^4+n^2}}{(n^3+1)(2^n + 3^n)}, \quad \frac{\sqrt{3^n+9^n}}{(4^n+8^n)^{1/3}}, \quad \sqrt{n+1} - \sqrt{n},

\displaystyle \frac{1}{n+\cos n}, \quad \frac{1}{n^{1+1/n}}, \quad \frac{e^{1/n}}{n^2}, \quad (n^3+n)^{1/3}-n.

Find the limit of the following sequences, as well as a simple equivalent if the limit is 0 or + \infty.

\displaystyle 2^n \sin(2^{-n}), \quad n^2 (e^{2/n} - 1), \quad \frac{2^{-n} + 3^{-n}}{\ln(1+3^{-n})}, \quad \sqrt{1+3/n} - 1,

\displaystyle \left ( 8 + \frac{1}{n^2} \right)^{1/3} - 2, \quad n \tan(1/n^2), \quad n \sin(1/\ln n),

\displaystyle \frac{\sin(1/n^2)(e^{1/n}-1)^2}{\ln(1+1/n^2)^2}, \quad 2^n\ln(1+\sin(1/n)), \quad \frac{\ln(n^2+\sqrt{n})}{\ln(2n^3+n^2)}.

Find the limit of the following sequences.

\displaystyle \left( 1 + \frac{1}{n^2} \right)^n, \quad \left( 1 + \frac{1}{n} \right)^{n^2}, \quad 2^{-n} \left( 2 + \sin\frac{1}{2n} \right)^n,

\displaystyle n^{1/(1+\ln n)}, \quad (e^n+2^n)^{1/n}, \quad \left ( \frac{4}{n} + 1 \right )^{1/\tan (1/n)}.

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s