4

Use mathematical induction to prove that for all integers $n \geq 4, 3^n \geq n^3$

So with this question I'd check the base case.

Suppose $P(4)$ is the predicate $3^4 \geq 4^3$, where $n \geq 4$

$81 \geq 64$, therefore $P(4)$ is true.

Suppose $P(k)$ is true for some predicate $3^k \geq k^3$, where $k \geq 4$

Consider $P(k+1).$

$3^{(k+1)} \geq (k+1)^3,$ where $k+1 \geq 4$

$3^k * 3$ $\geq$ $k^3+3k^2+3k+1$

I know I need to be moving towards proof using my $P(k)$ case but don't know how to move forward with the cubic function. This problem would be more understandable if I could work with a quadratic instead haha.

Any help/solutions appreciated. Have a good one!

xxxxxxxxx
  • 13,302
99 Fishing
  • 245

2 Answers2

1

\begin{align} 3^{n+1} &\geq 3n^3\\ &=n^3+2n^3\\ &=n^3+2n.n^2\\ &\geq n^3+2n(2n-1)\\ &=n^3+4n^2-2n\\ &>n^3+3n^2+3n+1\\ &=(n+1)^3 \end{align}

Nosrati
  • 29,995
  • How do you argue that $n^3+4n^2-2n > n^3+3n^2+3n+1$? This is, for example, not true for $n=4$ or $n=5$. – xxxxxxxxx Oct 02 '17 at 04:45
  • That's true for $n\geq6$. the cases $n=4,5$ obtain simply. – Nosrati Oct 02 '17 at 04:46
  • I'm not clear on how the n=4 (or 5) cases obtain simply, my understanding is much below you two here in the comments but how could I continue past $n^3+4n^2-2n>n^3+3n^2+3n+1$ when this isn't even holding for the P(4) predicate? @MyGlasses – 99 Fishing Oct 02 '17 at 04:56
  • $3^4>4^3$ and $3^5>5^3$. It's not necessary to start your formula just right after $4$. you can do parts of induction manually!! – Nosrati Oct 02 '17 at 05:01
  • Ah yup, that makes sense, thank you for the the insight and answer! – 99 Fishing Oct 02 '17 at 05:29
0

There is no cube in this problem, because

$$3^n\ge n^3\iff\left(\sqrt[3]3\right)^n\ge n.$$

Now it is an easy matter to see that

$$\left(\sqrt[3]3\right)^n\ge n\implies\left(\sqrt[3]3\right)^{n+1}\ge \sqrt[3]3\,n\ge n+1$$ as of $n=3$.