# Even More Induction

1. Jun 23, 2008

### Moridin

1. The problem statement, all variables and given/known data

Show that

$$\forall n \in \mathbb{N}: 3^{n} \geq n^{3}$$

3. The attempt at a solution

(1) Show that it is true for n = 1:

$$3^{1} \geq 1^{3}$$

(2) Show that if it is true for n = p, then it is true for n = p + 1:

Assume that $$3^{p} \geq p^{3}$$

Now,

$$3^{p+1} = 3 \cdot 3^{p} = 3^{p} + 3^{p} + 3^{p}$$

$$(p+1)^{3} = p^{3} + 3p^{2} + 3p + 1$$

Given our assumption, we know that if it could be demonstrated that

$$3^{p} + 3^{p} \geq 3p^{2} + 3p + 1$$

then we are done. From here, I'm not sure how to proceed. Should I pull some moves from analysis and argue that certain functions grow faster than others above a certain n? The last inequality is also a stronger criteria, but does not apply to p = 1 or p = 2, since 3^{p} was larger than p^{3}.

2. Jun 23, 2008

### dynamicsolo

Why not just compare

$$3^{p} + 3^{p} + 3^{p}$$

term-by-term with

$$p^{3} + 3p^{2} + (3p + 1)$$ ?

You've assumed

$$3^{p} \geq p^{3}$$

and, beyond some low value of p,

$$3^{p} \geq 3p^{2}$$

and

$$3^{p} \geq 3p+1$$.

EDIT: the last two inequalities only fail for p = 1, but you've already shown that the proposed inequality works there. As for showing that the inequalities work for p>= 2,
how about taking log base 3 of both sides?

Last edited: Jun 23, 2008
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?