1
$\begingroup$

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.

  • 1
    I think the new one makes more sense.2011-10-15

5 Answers 5

7

Let $f(n)=9n^3-3$ and $g(n)=8^n$. Certainly $f(0) and $f(1). Assume that $f(n), and we wish to show that $f(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.

  • 0
    I knew it didn't hold for $n=2$, but I didn't want to do the *whole* homework problem!2012-03-05
1

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.

1

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$.

1

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.

0

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$.

  • 1
    I have tried it out before and found out it is true for n ≥ 3 (or in fact, for n ≠ 2).2011-10-15