Question on induction

Question

For which $n\geq0$ is $3^n>n^3$ valid? Consider the four first cases: $$3^0=1>0$$ $$3^1=3>1^3$$ $$3^2=9>2^3$$ $$3^3=27\ngtr3^3$$

So let us consider the base case $k=4$:

$$3^4=81 >4^3,$$

which holds. Then we need to show $3^{k+1}>(k+1)^3 $

$3k^3>(k+1)^3\iff \left(1+\frac1k\right)^3<3$

For $k=3,\left(1+\frac1k\right)^3=\frac{64}{27}<3$

and $\left(1+\frac1{k+1}\right)^3<\left(1+\frac1k\right)^3$

$\implies \left(1+\frac1k\right)^3<3$ for $k\ge3$

Hence for the values $n=1,2$ and for $n>3$, $3^n>n^3$ holds. For $n=3$ we have strict equality, that is $3^n=n^3$. \

But there is a problem,

$3k^3>(k+1)^3\iff \left(1+\frac1k\right)^3<3$

is probably incorrect, but it gives the right result!

What is the correct step of this induction?

Answer 1

$\rm {Task :}$

Let $n$ be a positive integer . Prove that, $3^n>n^3$ holds $\forall n≥4$ by induction .

---

For $n=4$, the statement is obviously correct .

Suppose that, the statement is correct for $n=k≥5$. Then we can write :

$$3^k-k^3=a,\thinspace a>0$$

$\rm{Inductive \thinspace\thinspace step\thinspace\thinspace .}$

For $n=k+1$ we have :

$$ \begin{align}&\thinspace\thinspace\thinspace3^{k+1}-(k+1)^3\\ =&\thinspace\thinspace\thinspace 3(a+k^3)-(k+1)^3\\ >&\thinspace\thinspace\thinspace 3k^3-(k+1)^3\\ ≥&\thinspace\thinspace\thinspace 3k^3-\left(k+\frac k5\right)^3\\ =&\thinspace\thinspace\thinspace \frac{159}{125}k^3\thinspace >\thinspace 0\end{align} $$

which completes the proof .

---

$\rm {Alternative \thinspace \thinspace methods \thinspace\thinspace .}$

You can also observe that, since

$$ \begin{align}&\sqrt [3]{3}-1>\frac 15\\ \iff &3>\left(1+\frac 15\right)^3\end{align} $$

Then, we have :

$$ \begin{align}&3k^3>(k+1)^3\\ \iff &k\sqrt [3]3>k+1\\ \iff &\underbrace k_{\color{#0a0}{≥}\color{#c00}{\thinspace 5}}\thinspace\thinspace\underbrace{\left(\sqrt [3]3-1\right)}_{\color{#0a0}{>}\color{#c00}{\thinspace\frac 15}}>1\thinspace\thinspace .\end{align} $$

---

Note that, we can also complete the proof using the method of Polynomial long division or Synthetic division :

$$ \begin{align}&\thinspace\thinspace\thinspace 3k^3-(k+1)^3\\ =&\thinspace\thinspace\thinspace 2k^3-3k^2-3k-1\\ =&{\thinspace\thinspace\thinspace\underbrace {(k\!-\!5)}_{\color{#0a0}{≥}\color{#c00}{\thinspace 0}}\thinspace\underbrace {(2k^2\!+\!7k\!+\!32)}_{\color{#0a0}{>}\color{#c00}{\thinspace 0}}\!+\!159}\\ ≥&\thinspace\thinspace\thinspace 159\thinspace>\thinspace 0\thinspace\thinspace .\end{align} $$

Answer 2

There are three parts of the proof by induction:

1. Base case: the first number considered which fulfils the property/equation/inequality to be proved. Here the base case is $n=4$, and the inequality to be proved is $3^n>n^3$, which is fulfilled by $n=4$ (because $81>64$). Note that we use the variable $n$ here, the same as in the original inequality. We do not need to use $k$ yet in this step.

2. Induction step: assuming the case $n=k$ is true, for any $k\ge 4$, we have to prove that the case $n=k+1$ is true.

First we assume the case $n=k$ is true, that is, we assume $$3^k>k^3.$$ From that assumption, we try to prove that $3^{k+1}>(k+1)^3$. Let's start by multiplying the assumed inequality by $3$: $$3^{k+1}>3k^3$$ Now consider that for every $k\ge 4$, $$\left(\frac{k+1}{k}\right)^3<3$$ which is equivalent to $$3k^3>(k+1)^3.$$ From the two inequalities obtained, we conclude $$3^{k+1}>(k+1)^3,$$ proving that the case $n=k+1$ holds.

3. The conclusion: As we see that the case $n=4$ holds, and for every $k\ge4$, the inequality $3^k>k^3$ implies $3^{k+1}>(k+1)^3$, we conclude that the inequality $3^n>n^3$ holds for every natural number $n\ge4$.