Skip to content

Comparisons and asymptotic estimates

Prerequisites

Objectives

At the end of this chapter you will be able to:

  • compare two infinitesimal or infinite sequences;

  • recognize asymptotic sequences, \(a_n \sim b_n\);

  • compute limits by replacing sequences with simpler asymptotic ones.

1. Comparisons and asymptotic estimates

  • We have seen that a sequence tending to \(0\) is an infinitesimal; a sequence that diverges (to \(\ip\), to \(\im\)) is called an infinity (infinite quantity).

  • When two sequences are both infinitesimals or both infinities, it is useful to be able to compare them, to understand which of the two tends “more rapidly” to \(0\) or to infinity.

Example 1: Infinities

Examples of infinities are the following sequences:

\[ \left\{\log n \right\}, \quad \left\{\sqrt{n} \right\}, \quad \left\{n^2 \right\}, \quad \left\{2^n \right\} \]

Example 2: Infinitesimals

Examples of infinitesimals are the following sequences:

\[ \left\{ \frac{1}{\log n} \right\}, \quad \left\{ \frac{1}{ \sqrt{n}} \right\}, \quad \left\{ \frac{1}{n^2} \right\}, \quad \left\{ \frac{1}{2^n} \right\} \]
  • Let \(\{a_n\}\) and \(\{b_n\}\) be two infinities; considering the limit of their ratio we have 4 cases:

    \[ \lim_{n \rightarrow +\infty} \frac{a_n}{b_n} = \begin{cases} 0 & {\rm ~~~~case~~1):~~} \{a_n\} {\rm ~~is~an~infinity~of ~\textbf{lower order } than~~} \{b_n\}\\ l \in \R, l \neq 0 & {\rm ~~~~case~~2):~~} \{a_n\} {\rm ~and~} \{b_n\} {\rm ~are~infinities~of~the~\textbf{same order}} \\ \pm \infty & {\rm ~~~~case~~3):~~} \{a_n\} {\rm ~~is~an~infinity~of ~\textbf{higher order } than~~} \{b_n\}\\ {\rm nonexistent} & {\rm ~~~~case~~4):~~} \{a_n\} {\rm ~and~} \{b_n\} {\rm ~are~not~comparable} \end{cases} \]
  • Let \(\{a_n\}\) and \(\{b_n\}\) be two infinitesimals (with \(b_n\) eventually different from zero); considering the limit of their ratio we have 4 cases:

    \[ \lim_{n \rightarrow +\infty} \frac{a_n}{b_n} = \begin{cases} 0 & {\rm ~~~~case~~1):~~} \{a_n\} {\rm ~~is~an~infinitesimal~of ~\textbf{higher order } than~~} \{b_n\}\\ l \in \R, l \neq 0 & {\rm ~~~~case~~2):~~} \{a_n\} {\rm ~and~} \{b_n\} {\rm ~are~infinitesimals~of~the~\textbf{same order}} \\ \pm \infty & {\rm ~~~~case~~3):~~} \{a_n\} {\rm ~~is~an~infinitesimal~of ~\textbf{lower order } than~~} \{b_n\}\\ {\rm nonexistent} & {\rm ~~~~case~~4):~~} \{a_n\} {\rm ~and~} \{b_n\} {\rm ~are~not~comparable} \end{cases} \]
  • The case

    \[ \frac{a_n}{b_n} \rr 1 \]

    is particularly important: in this case we say that the two sequences \(\{a_n\}\) and \(\{b_n\}\) are asymptotic (asymptotically equivalent).

  • To indicate this, we write

    \[ a_n \thicksim b_n \]

    (read: \(a_n\) is asymptotic to \(b_n\))

  • The asymptotic symbol is very useful in computing limits, thanks to the following properties:

Proposition 1: Asymptotic behavior

  1. If \(a_n \thicksim b_n\), the two sequences have the same behavior:

    • either they converge to the same limit,

    • or they both diverge to \(\pm\infty\),

    • or neither of them has a limit.

  2. We can write chains of asymptotic relations, i.e.:

    \[ {\rm if~~} a_n \thicksim b_n \thicksim \dots \thicksim c_n {\rm ~~~~then~~~~} a_n \thicksim c_n \]
  3. An expression made of a product or quotient of several factors can be estimated factor by factor:

    \[ {\rm if~~} a_n \thicksim a'_n, b_n \thicksim b'_n, c_n \thicksim c'_n {\rm ~~~~then~~~~} \frac{a_n \: b_n}{c_n} \thicksim \frac{a'_n \: b'_n}{c'_n} \]
    • Warning: the same does not hold for sums or for exponentials.
Proof
  1. We prove the first statement

    \[ {\rm if~} a_n \thicksim b_n {\rm~then~} \{a_n\} {\rm~and~} \{b_n\} {\rm ~~have~the~same~behavior} \]
    • If \(a_n \rr l \in \R\), since

      \[ b_n = \frac{b_n}{a_n} \cdot a_n {\rm~~and~~} \frac{b_n}{a_n} \rr 1 \quad ({\rm by~definition~of~asymptotic}), \]

      then by the theorem on the algebra of limits we have

      \[ b_n \rr 1 \cdot l = l. \]
    • With the same steps, the theorem on the partial arithmetization of the infinity symbol allows us to conclude that

      \[ {\rm if~~} a_n \rr \pm \infty {\rm~~~and~~~} a_n \thicksim b_n {\rm~~~then~~~} b_n \rr \pm \infty. \]

    Observing that the asymptotic relation is symmetric, what we have just proved also shows that if \(\{b_n\}\) converges (diverges), then \(\{a_n\}\) converges (diverges) as well.

    • We conclude that if \(\{a_n\}\) is irregular, then \(\{b_n\}\) is irregular as well, because if, by contradiction, it were not, then by what we have just proved \(\{a_n\}\) would also be convergent or divergent.
  2. We prove the transitivity of the asymptotic relation:

    \[ {\rm if~~} a_n \thicksim b_n \thicksim c_n {\rm ~~~~then~~~~} a_n \thicksim c_n. \]

    The hypotheses mean that

    \[ \frac{a_n}{b_n} \rr 1 {\rm~~and~~} \frac{b_n}{c_n} \rr 1 \]

    Then by the theorem on the algebra of limits we have

    \[ \frac{a_n}{c_n} = \frac{a_n}{b_n} \cdot \frac{b_n}{c_n} \rr 1. \]
  3. The third property is proved analogously. □

Example 3: Asymptotic sequences by applying the definition

We prove that:

\[ \log n \thicksim \log (n+1) \]

Factoring out \(n\) in the second sequence we obtain

\[ \log (n+1) = \log \left(n \: \left(1 + \frac{1}{n} \right)\right)= \log n + \log \left(1+\frac{1}{n}\right) \]

Hence

\[ \lim_{n \rr \ip} \frac{\log n}{\log (n+1)} = \lim_{n \rr \ip} \frac{\log n}{\log n + \underbrace{\log \left(1+\frac{1}{n}\right)}_{\rr 0}} =1 \]
  • A typical way to show that

    \[ a_n \thicksim b_n \]

    consists in writing

    \[ a_n = b_n \: c_n {\rm ~~~with~~~} c_n \rr 1. \]

    That is, decomposing \(\{a_n\}\) into the product of a sequence \(\{b_n\}\) and a sequence \(\{c_n\}\) that tends to 1.

Example 4: Asymptotic sequences via the decomposition method

Example:

\[ \underbrace{2 \: n^2+ 3\:n +1}_{a_n} = ~~\underbrace{2 \: n^2}_{b_n} ~~ \underbrace{\left( 1 + \frac{3}{2\:n} + \frac{1}{2\: n^2}\right)}_{c_n} \thicksim 2\: n^2 \quad {\rm ~~hence~~} a_n \thicksim b_n \]

since

\[ \underbrace{\left( 1 + \frac{3}{2\:n} + \frac{1}{2\: n^2}\right)}_{c_n} \rr 1 \]

Example 5: Computing limits with asymptotic estimates

We compute the limit

\[ \lim_{n \rr \ip} \frac{2\:n^3+4n+1}{5\:(n+1)^3}= \left[\frac{\infty}{\infty}\right] \qquad {\rm~~(indeterminate~form)} \]

Proceeding as before we can write

\[ \underbrace{2 \: n^3+ 4\:n +1}_{a_n} = ~~\underbrace{2 \: n^3}_{a'_n} ~~ \underbrace{\left( 1 + \frac{2}{n^2} + \frac{1}{2\: n^3}\right)}_{\rr 1} \thicksim 2\: n^3 \]
\[ 5\:(n+1)^3= \underbrace{5 \: (n^3 + 3\:n^2 + 3 \:n +1)}_{c_n} = ~~\underbrace{5 \: n^3}_{c'_n} ~~ \underbrace{\left( 1 + \frac{3}{n} + \frac{3}{n^2} + \frac{1}{n^3}\right)}_{\rr 1} \thicksim 5\: n^3 \]

Using point 3 of Proposition Proposition 1 on asymptotic behavior we can write:

\[ {\rm if~~} a_n \thicksim a'_n, c_n \thicksim c'_n {\rm ~~~~then~~~~} \frac{a_n}{c_n} \thicksim \frac{a'_n}{c'_n} \]

and obtain

\[ \frac{2\:n^3+4n+1}{5\:(n+1)^3} \thicksim \frac{2\:n^3}{5\:n^3} \]

that is, the two sequences have the same behavior. Hence

\[ \lim_{n \rr \ip} \frac{2\:n^3+4n+1}{5\:(n+1)^3}= \lim_{n \rr \ip} \frac{2\:n^3}{5\:n^3} = \frac{2}{5} \]
  • Another way to show that

    \[ a_n \thicksim b_n \]

    is to use the substitution principle.

  • For the logarithm the substitution principle reads as follows: if

    \[ a_n \thicksim b_n {\rm ~~~~and~~~~} \lim_{n \rr \ip} b_n = \ip \qquad {\rm then} \qquad \log a_n \thicksim \log b_n \]
  • Indeed, since \(a_n \thicksim b_n\), we have \(\frac{a_n}{b_n} \rr 1\) and therefore \(\log \frac{a_n}{b_n} \rr \log 1 = 0\). We can then write:

    \[ \frac{\log a_n}{\log b_n} = \frac{\log \left( b_n \: \frac{a_n}{b_n}\right)}{\log b_n} = \frac{\log b_n + \log \frac{a_n}{b_n}}{\log b_n} = 1 + \frac{\overbrace{\log \frac{a_n}{b_n}}^{\rr 0}}{\underbrace{\log b_n}_{\rr \ip}} \rr 1 \]
  • Warning: it is not enough that two sequences both diverge to \(\ip\) for them to be asymptotic. For example \(\log n\) and \(\log e^n = n\) both diverge to \(\ip\), but

    \[ \lim_{n \rr \ip} \frac{\log n}{n} = 0 \neq 1 \]

    hence \(\log n\) and \(\log e^n\) are not asymptotic.

Example 6: Computing limits with the substitution principle and asymptotic estimates

We compute the limit

\[ \lim_{n \rr \ip} \log_3 (n^2 + 4n +1) \]

using the substitution principle and asymptotic estimates. With the decomposition method we have

\[ \underbrace{n^2 + 4\:n +1}_{a_n} = \underbrace{n^2}_{b_n} \: \underbrace{\left( 1 + \frac{4}{n} + \frac{1}{n^2}\right)}_{\rr 1} \thicksim n^2 {\rm ~~~~and~~~~} \lim_{n \rr \ip} n^2 = \ip \]

then, by the substitution principle,

\[ \log_3 (n^2 + 4\:n +1) \thicksim \log_3 \left(n^2\right) = 2 \: \log_3 n \]

and hence

\[ \lim_{n \rr \ip} \log_3 (n^2 + 4\:n +1) = \lim_{n \rr \ip} 2 \: \log_3 n =\ip \]

The fact that the asymptotic relation satisfies the 3 properties:

  1. Reflexive: \(a_n \thicksim a_n\)

  2. Symmetric: if \(a_n \thicksim b_n\) then \(b_n \thicksim a_n\)

  3. Transitive: if \(a_n \thicksim b_n\) and \(b_n \thicksim c_n\) then \(a_n \thicksim c_n\)

means that “asymptotic” is an equivalence relation.

2. In summary

In summary

  • \(a_n \sim b_n\) when \(a_n / b_n \to 1\).

  • In products and quotients a sequence can be replaced by an asymptotic one without changing the limit.

  • In sums the replacement is not allowed in general.


Exercises on this chapter: Computing limits of sequences