Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
I think the new one makes more sense. –  smanoos Oct 15 '11 at 0:08
show 2 more comments

5 Answers 5

up vote 7 down vote accepted

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.

share|improve this answer
2  
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
2  
@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
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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