3
$\begingroup$

How do I determine which number is bigger as $n$ gets sufficiently large, $2^n$ or $n^ {1000}$?

It seems to me it is a limit problem so I tried to tackle it that way.

$$\lim_{n\to \infty} \frac{2^n}{n^{1000}}$$

My thoughts are that, after some $n$, the numerator terms will be more than the terms in the denominator so we'll have something like $$\frac{\overbrace{2\times 2\times\cdots \times 2}^{1000\text{ factors}}}{n\times n \times \cdots \times n} \times 2^{n-1000}$$ At this point, I was thinking of using the fact that $2^n$ grows faster slower than $n!$ as $n$ gets larger so the limit, in this case, will be greater than $1$, meaning $2^n$ is bigger than $n^{1000}$ for sufficiently large $n$. This conclusion is really just a surmise based on a non-concrete formulation. Therefore, I'd appreciate any input on how to tackle this problem.

$\endgroup$
3
  • 2
    $\begingroup$ Exponential terms grow faster than polynomial terms for sufficiently large $n$. Also, $2^n$ does not grow faster than $n!$. $\endgroup$ – greelious Dec 6 '18 at 15:58
  • $\begingroup$ I mixed up the two, thanks. I'll edit it. $\endgroup$ – E.Nole Dec 6 '18 at 16:00
  • 2
    $\begingroup$ See related question/answers $\endgroup$ – farruhota Dec 6 '18 at 16:56
4
$\begingroup$

Note that$$\frac{2^{n+1}}{2^n}=2\text{ whereas }\frac{(n+1)^{1\,000}}{n^{1\,000}}=\left(1+\frac1n\right)^{1\,000}.$$Since$$\lim_{n\to\infty}\left(1+\frac1n\right)^{1\,000}=1<2,$$you have that$$\left(1+\frac1n\right)^{1\,000}<\frac32$$if $n$ is large enough.It's not hard to deduce from this that $2^n>n^{1\,000}$ if $n$ is large enough.

$\endgroup$
4
  • $\begingroup$ I'd like to clarify what the first line says about the two expressions. What I can deduce is that the purpose of the first line is to show that $2^n$ is increasing at a constant rate whereas $n^{1000}$ starts to slow down in terms of increase rate. Is that so? $\endgroup$ – E.Nole Dec 6 '18 at 16:20
  • $\begingroup$ It is more precise than that but, yes, it includes that. $\endgroup$ – José Carlos Santos Dec 6 '18 at 16:23
  • $\begingroup$ Well, what more does it say? I'm trying to understand your motivation for that approach. $\endgroup$ – E.Nole Dec 6 '18 at 16:27
  • 1
    $\begingroup$ It says that, after a certain point, the sequence $(n^{1\,000})_{n\in\mathbb N}$ grows slower than the sequence $(2^n)_{n\in\mathbb N}$. $\endgroup$ – José Carlos Santos Dec 6 '18 at 16:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.