4

The question is prove by induction that $n^3 < 3^n$ for all $n\ge4$.

The way I have been presented a solution is to consider:

$$\frac{(d+1)^3}{d^3} = (1 + \frac{1}{d})^3 \ge (1.25)^3 = (\frac{5}{4})^3 = \frac{125}{64} <2 < 3$$

Then using this $$(d+1)^3 = d^3 \times \frac{(d+1)^3}{d^3} < 3d^3 < 3 \times 3^d = 3^{d+1}$$ so we have shown the inductive step and hence skipping all the easy parts the above statement is true by induction.

However I don't find this method very intuitive or natural; is there another way to attack this problem?

The approach I wish to take involves starting from $$ 3^{d+1} = 3 \times3^d > 3d^3$$ but then I do not know how show further that $3d^3 > (d+1)^3 $ to complete the inductive step. I have looked around at the proofs related to showing that $2^n > n^2 $ inductively for $n \ge 5$ but cannot relate the proof for that case to this case.

Also, is there a more general method that could be used to solve, say $a^n > n^a $ for $ n \ge k $ for some $k\in \Bbb R$

Chill2Macht
  • 20,920
user258521
  • 1,001
  • You actually proved $3d^3>(d+1)^3$ in the first formula you've wriiten in the question, didn't you? – Cave Johnson Dec 22 '16 at 12:10
  • Is there another way of showing this inductively though? – user258521 Dec 22 '16 at 12:17
  • I agree with your method, but did you really prove that the factor of increase for the LHS < 3? $F= \frac{(d+1)^3}{d^3} = (d^3 + 3d^2 + 3d + 1) / d^3 = 1 + 3/d + 3 / d^2 + 1/d^3 $

    $for d = 4 : F < 3$

    then show that the function is decreasing , so F<3 for n >=4

     – Cato Dec 22 '16 at 13:19

4 Answers4

5

You need to show that

$$n^3<3^n\implies (n+1)^3<3^{n+1}$$

which amounts to

$$n^3<3^n\implies n^3<3\left(\frac n{n+1}\right)^33^n.$$

As $3\left(4/5\right)^3>1$ and the ratio is growing, the claim holds.

4

First, show that this is true for $n=4$:

$4^3<3^4$

Second, assume that this is true for $n$:

$n^3<3^n$

Third, prove that this is true for $n+1$:

$(n+1)^3<$

$(n+\frac14n)^3=$

$(\frac54n)^3=$

$\frac{125}{64}n^3<$

$\frac{128}{64}n^3=$

$2\color\red{n^3}<$

$2(\color\red{3^n})<$

$3(3^n)=$

$3^{n+1}$

Please note that the assumption is used only in the part marked red.

barak manos
  • 43,109
2

This base case holds because $4^3 < 3^4$.

To show that the inductive step holds, we need to show that:

$(n + 1)^3 < 3^{n + 1}$ holds if $n^3 < 3^n$ holds.

Note that:

$3^{n + 1} = 3 * 3^n > 3n^3$(since $3^n > n^3$ by the inductive hypothesis) > $(n + 1)^3$.

By binomial expansion: $(n + 1)^3 = n^3 + 3n^2 + 3n + 1$.

So:

$3n^3 ≥ (n + 1)^3\Leftrightarrow 3n^3 ≥ n^3 + 3n^2 + 3n + 1 \Leftrightarrow 2n^3 - 3n^2 - 3n - 1 ≥ 0. $

Since $2n^3 - 3n^2 - 3n - 1 = 0$ has a real solution at about $n \approx 2.26$ and $f(3) > 0$, we see that $2n^3 - 3n^2 - 3n - 1 > 0$ holds on the interval $(2.26,\infty)$. Then, because $4^3 < 3^4$, we see that:

$$3^{n + 1} > (n + 1)^3$$ for all $n \geq 4$, which is what we wanted to show.

Hope it helps.

  • I dont know how I would find the root to the cubic without using numerical approximations or else but surely there is an easier way to show that the cubic $ 2n^3 -3n^2 -3n -1$ is greater than 0. – user258521 Dec 22 '16 at 12:26
  • For writing this implies sign you have to writing \implies – Blaise Thunderstorm Dec 22 '16 at 12:26
  • @Blaise Thunderstorm Thank you. I have corrected it. –  Dec 22 '16 at 12:31
  • The base case needs to be $n=4$, not $n=1$. –  Dec 22 '16 at 12:46
  • First of all, you need to change that "$\implies$" to "$\iff$". Otherwise, you're assuming $3n^3>(n+1)^3$ instead of proving it. Second, IMO, this proof is a little to "clumsy" (as in "over-complicated", not in a negative manner). First, because of your logical inference (which although correct, feels kinda "unorganized"). But most important, because your approach forces you to rely on polynomial analysis, which can easily be avoided. – barak manos Dec 22 '16 at 13:20
  • I feel like this proof was stolen from Yahoo as well because I read the exact same thing on Yahoo. – user258521 Dec 22 '16 at 14:04
1

The best solution that I can produce using some of the ideas from above is:

Proving the base case :

For $n=4$, we have $P(4): 3^4 > 4^3 \Leftrightarrow 81 > 64$ which is true.

Assume that the inequality is true for some d:

Assume $P(d): 3^d > d^3$.

Then show that $P(d+1)$ is true:

$P(d+1): 3^{d+1} > (d+1)^3 $

Starting from the RHS, $$(d+1)^3 = d^3 + 3d^2 + 3d +1 < 3^d + 3d^2 + 3d +1 $$ (using our inductive hypothesis)

Now if we can prove $3d^2 + 3d +1 < 3^d$ then we will be done.

So attempting to do this using induction again;

First if we prove that $6n+6 < 3^n$, we will be able to use this result later.

Proving the base case:

For $n=4$, $$6(4)+6 <3^4 \Leftrightarrow 30 < 81 $$ which is true.

Assume that the inequality is true for some j:

Assume $P(j): 6j+6 <3^j$

Then show that $P(j+1)$ is true:

$P(j+1): 6(j+1) +6 = 6j +6 +6 < 3^j+6 < 2(3^j) <3^{j+1}$

as $j \ge 4$ so 3^j > 6 for all j.

Thus, $6n+6 < 3^n$ is true for all $n \ge 4$.

Next, proving the base case for $3n^2 + 3n +1 < 3^n$:

For $n=4$, $$3(4^2) +3(4)+1 <3^4 \Leftrightarrow 61 < 81 $$ which is true.

Assume that the inequality is true for some k:

Assume $P(k): 3k^2 +3k +1 <3^k$

Then show that $P(k+1)$ is true:

$$P(k+1): 3(k+1)^2 +3(k+1) +1 = 3k^2 +3k +1 +(6k+6) < 3^k + 6k+6 < 2(3^k) <3^{k+1}$$

Therefore $3n^2 + 3n +1 < 3^n$ is true for all $n \ge 4$.

Going back to the question now,

$(d+1)^3 <3^d + 3d^2 +3d+1 <3^d +3^d <3^{d+1}$

So $3^n < n^3 $ for all $n \ge 4$ by mathematical induction! Although the working out for this approach is very long winded I find that it is more logical to a beginner at induction.

user258521
  • 1,001