Sequence $\left(\frac{k^n}{2^k}\right)$ convergence through epsilon proof.

Question

Prove that, for any $n\in\mathbb{N}$, $$\lim_{k\to\infty} \frac{k^n}{2^k} = 0$$ using an $\epsilon-$proof.

As scratchwork, I've gotten to $$\left|\frac{k^n}{2^k} - 0\right| = \frac{k^n}{2^k}\leq \epsilon$$

but I don't know how to get farther. I understand that if I can find a way to solve for k as a "function" of epsilon, then I can complete the proof. This is the part that I'm stuck on. We don't have many tools available yet, since we have only established the rational numbers and the concept of sequence convergence.

Answer 1

Let $k\gt 2n$. Using the binomial expansion of $(1+1)^k$ we find that $$(1+1)^k \gt \frac{(k)(k-1)(k-2)\cdots (k-n)}{(n+1)!}$$ ($n+1$ terms).

Each of $k-1$, $k-2$, and so on up to $k-n$ is bigger than $k/2$. Thus $$(1+1)^k \gt k \cdot \frac{k^n}{2^n(n+1)!}.$$ It follows that $$\frac{k^n}{2^k}\lt \frac{2^n(n+1)!}{k}.$$ This inequality is strong enough to prove convergence to $0$. If $K\gt 2n$ and $K\gt \frac{2^n(n+1)!}{\epsilon}$, and $k\gt K$, then the $k$-th term of your sequence is less than $\epsilon$.

Answer 2

Recall that the logarithm function satisfies the inequality

$$\log(x)\le \frac{x^{\alpha}}{\alpha}$$

for $x>0$ and any $\alpha >0$. Let us choose (arbitrarily) $\alpha =1/2$. Then, we have

$$\log(x)\le 2\sqrt{x}$$

Note that the sequence of interest then satisfies the inequality

$$\begin{align} \frac{k^n}{2^k}&=e^{n\log(k)-k\log(2)}\\\\ &\le e^{2n\sqrt{k}-k\log(2)}\\\\ &=e^{n^2/\log(2)}e^{-\log(2))(\sqrt k - n/\log(2))^2}\\\\ &<\epsilon \end{align}$$

whenever $k>\left(\frac{n}{\log(2)}+\sqrt{\left(\frac{n}{\log(2)}\right)^2-\frac{\log(\epsilon)}{\log(2)}}\right)^2$.

And we are done!

Answer 3

One can also reduce this problem to a simpler, already understood, base case. Since $$ \left(1+\frac1n\right)^n>1+n·\frac1n=2 $$ we get $$ \frac{k^n}{2^k}\le \left(\frac{k}{(1+\alpha)^k}\right)^n $$ with $α=\frac1n$. For the inner sequence one gets for $k\ge 2$ $$ \frac{k}{(1+\alpha)^k}\le\frac{k}{\binom{k}{2}α^2}=\frac{2n^2}{k-1} $$ Thus to get an upper bound of $\varepsilon>0$ for the original sequence one needs, in a very generous chain of bounds, $$ k>1+\frac{2n^2}{\sqrt[n]ε} $$

Answer 4

Taking logs, we want to show that $k \ln 2 - n\ln k \to \infty$ as $k \to \infty$.

Since $n$ is fixed, this is the same as $\frac{k}{\ln k} \to \infty$.

There are many ways of showing this. Here is an easy one that uses only the definition of $\ln$ and leads to the inequality stated by Dr. MV.

If $a > 0$ then

$\begin{array}\\ \ln(k) &=\int_1^k \frac{dt}{t}\\ &\le\int_1^k \frac{dt}{t^{1-a}}\\ &=\int_1^k t^{a-1}dt\\ &=\frac{t^{a}}{a}|_1^k\\ &=\frac{k^{a}-1}{a}\\ &<\frac{k^{a}}{a}\\ \end{array} $

Therefore $\frac{k}{\ln k} \gt \frac{k}{k^a/a} =ak^{1-a} $ for any $a > 0$.

If $a < 1$, then this is unbounded.

The usual special case is $a = 1/2$ which leads to $\ln k < 2\sqrt{k}$ so $\frac{k}{\ln k} \gt \sqrt{k}/2 $.

Note that by taking $a$ small, this shows that $\frac{\ln k}{k^a} \to 0$ for any $a > 0$ as $k \to \infty$.

Here's the details, which involve a fairly standard trick.

We have $\ln k \lt \frac{k^{a/2}}{a/2} = k^a\frac{2k^{-a/2}}{a} $ so $\frac{\ln k}{k^a} \lt \frac{2}{ak^{a/2}} \to 0$ as $k \to \infty$.