1
$\begingroup$

Use induction to show that $3^n >n^3$ for $n≥4$. (Note that you have to start at $n=4$ as the result isn't true for $n=3$ !)

I am very new to using induction, but as I understand it I have to do the following:

  1. Show that it is true for the base case, when $n=4$, so $ 3^4 > 4^3$, which is indeed true.
  2. Assume that for $n=k$, that $3^k>k^3$ for $k\ge 4$ (The induction hypothesis).
  3. Then you show that the hypothesis being true at some k implies that it holds at $n=k+1$.

So what I have to do is show that $3^{k+1}>(k+1)^3$.

I don't know where to begin.

I know that $(k+1)^3 = k^3+3 k^2+3 k+1$ and that $3(3^k) = 3^{k+1}$ but no idea how to proceed.

$\endgroup$

5 Answers 5

3
$\begingroup$

You get $3^{n+1}$ from $3^n$ by multiplying by $3$. You get $(n+1)^3$ from $n^3$ by multiplying by $(n+1)^3/n^3$. Thus all you need to do is to show that $$ 3>\left(\frac{n+1}n\right)^3. $$ Hint for this: What happens to the fraction $(n+1)/n$ as $n$ grows?

$\endgroup$
2
$\begingroup$

Indeed $3^{k+1} = 3(3^k)$ $ \gt 3*(k)^3 $ (By the Inductive Hypothesis) $ \qquad\qquad\space = k^3 + 2k^3\gt k^3 + 3k^2 + 3k + 1 = (k+1)^3$

You have already shown the base case, and the inductive hypothesis. Above is how to show the k+1st step.

If you think that saying $2k^3 > 3k^2 + 3k + 1$ is to much of a giant leap, then you can prove it by induction too for $k \ge 4$

$\endgroup$
1
$\begingroup$

Hint: prove that $3k^3>(k+1)^3$ for $k \geq 4$.

$\endgroup$
0
$\begingroup$

So if I have understood the kind answers given above, an answer could be:

$3^{k+1} = 3(3k)$ > $3*k^3$ (By the inductive hypothesis).

Because $3^{k+1} > 3*k^3 $, if I can prove that $3k^3> (k+1)^3$, then I have proved that $3^{k+1}>(k+1)^3$ (for $k \ge 4$).

$3k^3 - (k+1)^3 = 2 k^3-3 k^2-3 k-1 > 0$ (for $k \ge 4$).

So $3k^3> (k+1)^3$ and I am done.

If this is incorrect please help me out!

$\endgroup$
0
0
$\begingroup$

Using your induction hypothesis, noting that $k\geq 4$,

$\begin{align*} 3^{k+1}&=3\cdot 3^k \\ &>3k^3\\ &=k^3+2k^3\\ &\geq k^3+8k^2\\ &=k^3+3k^2+5k^2\\ &\geq k^3+3k^2+20k\\ &=k^3+3k^2+3k+17k\\ &>k^3+3k^2+3k+1\\ &=(k+1)^3. \end{align*}$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .