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.
Thanks in advance.
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.
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$.
