# Prove for which $n \in \mathbb{N}$: $9n^3 - 3 ≤ 8^n$

A homework assignment requires me to find out and prove using induction for which $n ≥ 0$ $9n^3 - 3 ≤ 8^n$ and I have conducted multiple approaches and consulted multiple people and other resources with limited success. I appreciate any hint you can give me.

-
It should be clear that $9n^3 - 3$ is increasing. You shouldn't expect it to be less than 8 for very long, right? –  Hans Parshall Oct 14 '11 at 23:54
I am sure this is only true for $n=1$ if $n$ is a natural number –  smanoos Oct 14 '11 at 23:55
Induction seems quite irrelevant, so much so that it seems doubtful that a problem that goes exactly as quoted was assigned. –  André Nicolas Oct 14 '11 at 23:58
I can assure you I was assigned the problem. Clarified that I only need natural numbers; Also good but not perfect would be a proof that it's true for n ≥ 3. –  Florian Mayer Oct 15 '11 at 0:01
I think the new one makes more sense. –  smanoos Oct 15 '11 at 0:08

Let $f(n)=9n^3-3$ and $g(n)=8^n$. Certainly $f(0)<g(0)$ and $f(1)<g(1)$. Assume that $f(n)<g(n)$, and we wish to show that $f(n+1)<g(n+1)$. Now, $f(n+1) = 9(n+1)^3-3 = f(n) \cdot \frac{9(n+1)^3-3}{9n^3-3}$, while $g(n+1)=8 g(n)$. So it will suffice to show that $$\frac{9(n+1)^3-3}{9n^3-3} < 8.$$ That's a polynomial equation (a cubic!), that I leave to the reader.

-
Simple computation shows it is not true for n=2, so you probably don't want to start induction at O. –  Thomas Andrews Oct 15 '11 at 1:07
Also, that it's false for n = 2 makes me wonder how any proof that does not take that into account can be correct. –  Florian Mayer Oct 15 '11 at 1:17
@Kevin: Welcome to MSE! –  JavaMan Oct 15 '11 at 7:02
How does it follow that the inequality is true for n=2 where obviously the statement isn't, but false at n=1 where the statement is? bit.ly/ndBnQX –  Florian Mayer Oct 15 '11 at 10:27
I knew it didn't hold for $n=2$, but I didn't want to do the whole homework problem! –  Kevin O'Bryant Mar 5 '12 at 3:22

Let $f(n)=n^3-3$, and let $g(n)=8^n$. We compute a little, to see what is going on.

We have $f(0) \le g(0)$; $f(1)\le g(1)$; $f(2) > g(2)$; $f(3) \le g(3)$; $f(4) \le g(4)$. Indeed $f(4)=573$ and $g(4)=4096$, so it's not even close.

The exponential function $8^x$ ultimately grows incomparably faster than the polynomial $9x^3-3$. So it is reasonable to conjecture that $9n^3-3 \le 8^n$ for every non-negative integer $n$ except $2$.

We will show by induction that $9n^3-3 \le 8^n$ for all $n \ge 3$. It is natural to work with ratios. We show that $$\frac{8^n}{9n^3-3} \ge 1$$ for all $n \ge 3$. The result certainly holds at $n=3$.

Suppose that for a given $n \ge 3$, we have $\frac{8^n}{9n^3-3} \ge 1$. We will show that $\frac{8^{n+1}}{9(n+1)^3-3} \ge 1$.

Note that $$\frac{8^{n+1}}{9(n+1)^3-3}=8 \frac{9n^3-3}{9(n+1)^3-3}\frac{8^n}{9n^3-3}.$$ By the induction hypothesis, we have $\frac{8^n}{9n^3-3} \ge 1$. So all we need to do is to show that $$8 \frac{9n^3-3}{9(n+1)^3-3} \ge 1,$$ or equivalently that $$\frac{9(n+1)^3-3}{9n^3-3} \le 8.$$ If $n\ge 3$, the denominator is greater than $8n^3$, and the numerator is less than $9(n+1)^3$. Thus, if $n \ge 3$, then $$\frac{9(n+1)^3-3}{9n^3-3} <\frac{9}{8}\frac{(n+1)^3}{n^3}=\frac{9}{8}\left(1+\frac{1}{n}\right)^3.$$ But if $n \ge 3$, then $(1+1/n)^3\le (1+1/3)^3<2.5$, so $\frac{9}{8}(1+1/n)^3<8$, with lots of room to spare.

-

Clearly, if $3n\le 2^n$ then $9n^3-3\le (3n)^3 \le (2^n)^3 = 8^n$.

So let us have a look at the (hopefully simpler) problem when $3n \le 2^n$. If we are able to solve this problem, only finitely many cases will remain to be checked.

Claim: $3n\le 2^n$ holds for every $n\in\mathbb N$, $n\ge 4$.

Proof by induction. $1^\circ$ For $n=4$ we have $3n = 12 \le 16 = 2^n$.

$2^\circ$. Suppose the claim is true for $n$, we will verify it for $n+1$.

$3(n+1)=3n\cdot\frac{n+1}n \le 2^n\cdot 2 = 2^{n+1}$.

We have used $3n\le 2^n$ (inductive hypothesis) and $\frac{n+1}n=1+\frac1n\le2$.

-

Let's try to find the $n$ such that the simpler inequality $9 n^3 < 8^n$ holds. If this is true, the desired inequality is true.

Computation will settle the smaller values.

Taking the cube root, this is the same as $n 9^{1/3} < 2^n$. Since $9^{1/3} < 3$, this is true when $3n < 2^n$.

This is true when $n=4$ ($12 < 16$). If is true for $n \ge 4$, $3(n+1) = 3n(1+1/n) < 2^n(1+1/4) \le 2^{n+1}$.

The result is thus true for $n \ge 4$. For $n=3$, $9 n^3-4= 239$ and $8^3 = 512$, so it is true. For $n=2$, $9 n^3-4 = 68$ and $8^2=64$ so it is false.

-

Hint: first, just try the first few $n$ so you can find out where it is true. Then you should be able to show that going from $n$ to $n+1$ the left side gets multiplied by something less than $8$.

-
I have tried it out before and found out it is true for n ≥ 3 (or in fact, for n ≠ 2). –  Florian Mayer Oct 15 '11 at 1:04