Several Limit Comparisons

Problem 1. Prove that $n^{1/n} \to 1$ as $n \to \infty$ .

Solution. We refer to this solution for inspiration.

It suffices to prove that $x_n := n^{1/n} - 1 \to 0$ . We first check that $x_n \geq 0$ since taking $n$ -th roots to the inequality $n \geq 1$ yields $n^{1/n} \geq 1^{1/n} = 1$ . We then employ the binomial theorem to obtain

$\displaystyle n = (1 + x_n)^n \geq 1 + nx_n + \frac{n(n-1)}{2} x_n^2 \geq \frac{n(n-1)}{2} x_n^2.$

By algebra,

$\displaystyle 0 \leq x_n^2 \leq \frac{2}{n-1}.$

Since $2/(n-1) \to 0$ , by the squeeze theorem, $x_n^2 \to 0$ , so that $x_n \to 0$ , as required.

Problem 2. Prove that for any sequence $x_n > 0$ , if $x_{n+1}/x_n \to x$ for some $0 \leq x < 1$ , then $x_n \to 0$ .

Solution. Fix $\epsilon = 1$ . Since $x_{n+1}/x_n \to x$ , for any $k> 0$ , there exists $N \in \mathbb N$ such that for $n \geq N$ ,

$\displaystyle \left| \frac{x_{n+1}}{x_n} - x \right| <k \cdot \epsilon.$

By algebra, $x_{n} < (x + k) \cdot x_{n-1}$ . Set $k := (1-x)/2$ so that $r := x+ k < 1$ . Then

$\displaystyle 0\leq x_{n} < rx_{n-1}< \cdots < r^{n-N} x_N= \frac{x_N}{r^{N}} \cdot r^n \to 0.$

By the squeeze theorem, $x_n \to 0$ , as required.

Problem 3. For non-negative functions $f, g$ such that $f(n) \to \infty$ and $g(n) \to \infty$ , denote $f \ll g$ to mean that as $n \to \infty$ , $f(n)/ g(n) \to 0$ .

For non-negative functions $f,g,h$ , prove that if $f \ll g$ and $g \ll h$ , then $f \ll h$ . In this regard we can write $f \ll g \ll h$ without contradiction.

Solution. Assume $f(n),g(n),h(n) \geq 1 > 0$ for large $n$ . We observe that

$\displaystyle \frac{f(n)}{h(n)} = \frac{f(n)}{g(n)} \cdot \frac{g(n)}{h(n)} \to 0 \cdot 0 = 0,$

so that $f \ll h$ , as required.

Problem 4. Fix $k > 1$ and $a > 1$ . Prove that $n^k \ll a^n$ .

Solution. Define $x_n := n^k/a^n$ . We observe that

$\displaystyle \begin{aligned} \frac{x_{n+1}}{x_n} &= \frac{(n+1)^k/a^{n+1}}{n^k/a^n} = \left(1 + \frac 1n\right)^k \cdot \frac 1a \to (1+0)^k \cdot \frac 1a = \frac 1a < 1.\end{aligned}$

By Problem 2, $x_n \to 0$ , which implies $n^k \ll a^n$ .

Problem 5. Fix $k > l > 1$ and $b > a > 1$ . Prove the common comparisons

$\log n \ll n \ll n \log n \ll n^k \ll n^l \ll a^n \ll b^n \ll n! \ll n^n.$

Here, $\log \equiv \ln$ by conventional mathematical notation.

Solution. To prove $\log n \ll n$ , we observe that by Problem 1,

$\displaystyle \begin{aligned} \frac{\log n}{n} &= \log (n^{1/n}) \to \log(1) = 0. \end{aligned}$

$n \ll n \log n$ is obvious since $1/{\log n} \to 0$ . Next, since $\log n \ll n$ ,

$\displaystyle \frac{ n \log n }{ n^k } = \frac{ \log n }{ n^{k-1} } = \frac 1{k-1} \cdot \frac{ \log(n^{k-1}) }{ n^{k-1} } \to \frac 1{k-1} \cdot 0 = 0.$

To prove $b^n \ll n!$ , define $x_n := b^n/n!$ . Then

$\displaystyle \frac{x_{n+1}}{x_n} = \frac{b}{n+1} \to 0 < 1,$

so that $x_n \to 0$ implies $b^n \ll n!$ . The final result follows from

$\displaystyle 0 \leq \frac{n!}{n^n} \leq \frac 1n \to 0.$

KindiakMath

Several Limit Comparisons

Leave a comment Cancel reply

Several Limit Comparisons

Share this:

Leave a comment Cancel reply