4
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

\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}

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Morgan Rodgers Oct 2 '17 at 4:45
  • $\begingroup$ That's true for $n\geq6$. the cases $n=4,5$ obtain simply. $\endgroup$ – Nosrati Oct 2 '17 at 4:46
  • $\begingroup$ 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 $\endgroup$ – 99 Fishing Oct 2 '17 at 4:56
  • $\begingroup$ $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!! $\endgroup$ – Nosrati Oct 2 '17 at 5:01
  • $\begingroup$ Ah yup, that makes sense, thank you for the the insight and answer! $\endgroup$ – 99 Fishing Oct 2 '17 at 5:29
1
$\begingroup$

You are making your proof awkward by writing down what you want to finish with, instead of your assumption (though it is good to have this written in your sidebar so you can see your goalpost).

You have $3^{(k+1)} = 3\cdot 3^{k}$, and by your assumption you have $3 \cdot 3^{k} \geq 3\cdot k^{3}$. So you want to show that $3k^{3} \geq k^{3}+3k^{2}+3k+1$. I hope this helps (you will need to use the fact that $k \geq 4$).

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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