How to reach from $2^{n} < n^{8}$ to $2 \leq n \leq 43$

Question

I've been looking for a method to discover how to find the range of values of $n$ that follow the $2^{n} < n^{8}$ inequality, other than brute checking every number.

Context: The question arises from an exercise provided by the book 'An Introduction to Algorithms', where the question asked is the following one:

For which values of n is $8n^2$ smaller than $64 * log_{2}(n)$?

I've tried simplifying and proceeded to try using the Lambert W function, but couldn't manage to separate adequately the n from the rest of the equation. Thus, I've decided to ask in a general manner the ways you could achieve the result by minimizing the manual number checking.

How should I proceed to arrive to the $2 \leq n \leq 43$ conclusion?

Edit, clarification: it is known from the beginning that the result must be an interval.

Answer 1

Using algebra.

Take logarithms and consider the function $$f(n)=\log \left(n^8\right)-\log \left(2^n\right)=8\log(n)-n\log(2)$$ It is obvious that $f(1)<0$ and $f(2)>0$. Concerning the derivatives $$f'(n)=\frac{8}{n}-\log (2)\qquad \text{and} \qquad f''(n)=-\frac{8}{n^2} \quad <0 \quad \forall n$$ The first derivative cancels at $n_*=\frac 8{\log (2)}$ and this corresponds to a maximum (second derivative test).

Now the only real solution of $f(n)=0$ for $n>1$ is given in terms of Lambert function $$f(n)=0 \implies n=-\frac{8 }{\log (2)}W_{-1}\left(-\frac{\log (2)}{8}\right)=43.56\cdots$$

Answer 2

Since the function $\log_2$ is increasing, you can say that $2^x<x^8 \iff x<\log_2 x^8 \iff \log_2 x^8 - x>0$ because $x \geq 1$, and $\log$ is defined there (we want in the end a solution within the positive integers). Now, define $f:\mathbb{R}_+^* \rightarrow \mathbb{R}$ as $f(x)=\log_2 x^8 - x$. We want to verify in which interval this is positive.

Note that $f(1)=-1<0$ and $f(2)=6>0$. Also, $f'(x)=\frac{8x^7}{x^8 \ln 2}-1=\frac{8}{x \ln 2}-1$. Now we need to see where $f'(x)$ is positive and where it is negative.

1. $f'(x)=0 \iff x=\frac{8}{\ln 2}$;
2. $f'(x)>0 \iff x<\frac{8}{\ln 2}$;
3. $f'(x)<0 \iff x>\frac{8}{\ln 2}$.

Hence, $f$ is increasing for $x<\frac{8}{\ln 2}$ and decreasing for $x>\frac{8}{\ln 2}$. But $f(2)>0$, so $f$ is positive at least until $x$ hits $\frac{8}{\ln 2}$. From there, $f$ will start descending. At some point, we will have $f(x)=0$. Here, because $f(44)<0$ and $f(43)>0$, you can use the Intermediate value theorem to conclude that $f(a)=0$ for some $a \in (43,44)$. Therefore $f(x)>0 \iff x\in [2,\cdots,a)$. Since we want integer solutions, just perform $[2,\cdots,a) \cap \mathbb{Z}=\{2,3,\cdots, 43 \}$.

Of course, this method requires you to calculate $f(x)$ until you reach some $n$ with $f(n)>0$ and $f(n+1)<0$, while you needed something not this brute. But I hope it helps anyway.

Answer 3

We can obtain some information about the possible range in a simple way as follows

$$2^{x} = x^{8} \iff x\log 2=8\log x \iff \frac{\log x}{x}=\frac{\log 2}{8}$$

and from here since

$$0=\frac{\log 1}{1}\le \frac{\log 2}{8}\le \frac{\log 2}{2}$$

we can guess that equality holds for $1<x<2$, and from

$$\frac 34 \frac{\log 2}{8}=\frac{\log 64}{64}\le \frac{\log 2}{8}\le \frac{\log 32}{32}=\frac 5 4\frac{\log 2}{8}$$

we can guess that equality holds also for $32<x<64$.

---

As an alternative, for the higher bound we can proceed as follows, since $2^{10}\approx 1000$ we have that

• $2^{10}\approx 10^3 <10^8$
• $2^{20}\approx 10^6 <20^8 \approx \frac1 4 10^310^8$
• $2^{30}\approx 10^9 <20^8<30^8 $
• $2^{40}\approx 10^{12} <40^8=4^810^8\approx 2^6 10^{11}$
• $2^{50}\approx 10^{15} >50^8= \frac1{2^8}100^8\approx 4 \cdot 10^{13}$

which restricts the range at $40<n<50$.

Answer 4

A way is to remark that the function $f(x)= 2^x\,x^{-8}$ is positive, tends to $+\infty$ by standard growth comparison, and is convex. Indeed, $$ f'(x) = f(x)\left(\ln(2) - 8/x\right) \\ f''(x) = f(x) \left((\ln(2) - 8/x)^2+8/x^2\right) > 0 $$ Since $f(1) = 2 > 1 > f(2)$, and the function can only cross the axis $y=1$ once (being convex) we deduce that $$ f^{-1}([0,1]) ⊂ [a,b] $$ with $a\in(1,2)$.

Now how to get an approximate value of $b$ without too many computations. You can start by computing at which point $c$ we have $f'(x)=0$, giving the minimum of $f$. We find $c = 8/\ln 2 > 11$, so in particular, $b> 11$.

You can also hope that it will give you an idea of the numbers you should consider to get an upper bound. Since we are dealing with an exponential type function, you can then try the next order of magnitude, so $x=100$, where one can find that $f(x) > 1$. Then you can proceed by dichotomy an just test the values: $x = 55, 33, 44$. Here you find that the value is quite close to $1$, so you try $43$, and you are done.

Answer 5

I'll take for granted that the set of natural numbers for which the inequality holds is an interval; both sides are strictly increasing and convex, and the left hand side eventually increases faster.

Note that $2^n\leq n^8$ if and only if $2^{\tfrac n8}\leq n$. This inequality is easy to evaluate for multiples of $8$; plugging in $n=8,16,24,\ldots$ it is easy to see that the inequality holds for $n=40$, but not for $n=48$.

If you know that $\sqrt2>1.4$ then it is also easy to see that the inequality fails for $n=44$ as $$2^{44/8}=2^5\sqrt2>32\cdot1.4=44.8>44.$$ Then it remains to check whether the inequality holds for $n=41,42,43$. If you first check $42$ you only need to check two of these three numbers. On the other hand the inequality only just fails for $n=44$, so I'd dare venture that it holds for $n=43$, and I'd check this one first.

---

To clarify the first paragraph: It is clear that both sides of the inequality are strictly increasing on the positive integers. For any positive integer $n$, increasing $n$ by $1$ increases the left- and right-hand sides by factors $$\frac{2^{n+1}}{2^n}=2\qquad\text{ and }\qquad\frac{(n+1)^8}{n^8}=\left(1+\frac1n\right)^8,$$ respectively. This shows that there is some positive integer $N$ sucht that the right hand side increases faster as long as $n\leq N$, and once $n>N$ the left hand side increases faster. It follows that the subset of positive integers that satisfy the inequality is an interval.