# Prove n^3 less than or equal to 3^n for n=1,2,

1. Oct 14, 2009

### naele

1. The problem statement, all variables and given/known data
Prove that $$n^3 \leq 3^n$$ for $n=1,2,...$

2. Relevant equations
Binomial theorem

3. The attempt at a solution
Check for P(1)= $$1^3 \leq 3^1$$. So the base case holds, now assume P(k) is true and show that it implies P(k+1).

By assumption $$3\cdot k^3 \leq 3\cdot 3^n$$. And this is where I get stuck because obviously $$(k+1)^3 \nleq 3k^3$$

2. Oct 14, 2009

### Office_Shredder

Staff Emeritus
If that last part is obvious, you should be able to prove it. It'll be tough...

Consider instead expanding (k+1) and finding an upper bound for that based on k3

3. Oct 14, 2009

### naele

Well it's not "obvious" but plotting $$3k^3 - (k+1)^3$$ shows negative values for positive k. On the other hand, I'm not sure what you mean by finding an upper bound.

Expanding gives $$k^3+3k^2 +3k+1$$. Comparing that with $$k^3 + k^3 +k^3$$. I could try a term by term comparison of $$3\cdot 3^k=3^k + 3^k +3 ^k$$. The first terms of each side are ok because that's by assumption. But $$3k^2 > 3^k$$ so hmmm.

4. Oct 14, 2009

### Office_Shredder

Staff Emeritus
If you can find a natural number k that breaks the inequality, you're done. You've proven the hypothesis to be false.

By inductive hypothesis
$$3k^2<k^3<3^k$$ as long as $k \geq 3$

So your base case is in fact going to be a couple of values of k, but that's not a real problem

5. Oct 14, 2009

### HallsofIvy

Staff Emeritus
Do you realize that you are saying that the very statement you are trying to prove is "obviously" false? $3k^3= k^{k+1}$ so if $(k+1)^3\nleq 3k^3= 3^{k+1}$ then $n^2< n^3$ is not true for all n.