4

Prove by mathematical induction that:

$$\forall n \in \mathbb{N}: 3^{n} > n^{3}$$

Step 1: Show that the statement is true for $n = 1$:

$$3^{1} > 1^{3} \Rightarrow 3 > 1$$

Step 2: Show that if the statement is true for $n = p$, it is true for $n = p + 1$

The general idea I had was to start with $(p+1)^{3}$ and during the process substitute in $3^{p}$ for $p^{3}$ as an inequality.

$$(p+1)^{3} = p^{3} + 3p^{2} + 3p + 1 < 3^{p} + 3p^{2} + 3p + 1$$

Now, if it can be shown that:

$$\forall p \in \mathbb{N}: 3p^{2} + 3p + 1 \leq 2 \cdot 3^{p}$$

...the proof is complete. This is because $3^{p+1} = 3 \cdot 3^{p}$ and one of those three have already been used.

We do this by mathematical induction. First, the base case of $n = 1$:

$$3\cdot 1^{2} + 3 \cdot 1 + 1 \not \leq 2 \cdot 3^{1}$$

..which turns out to be false.

What are some more productive approaches to this step?

Martin Sleziak
  • 53,687
MathInferno
  • 1,186
  • 2
    Start the induction with $n=3$, and check the $n=1,2$ cases separately. – AMPerrine Mar 08 '15 at 00:47
  • It is false exactly for $p=1$ since in that case, you go from $3>1$ to $9>8$, so the difference between the two sides decreases. You therefore get that $3\cdot 1^2 + 3\cdot 1 + 1 = 7$ is one too large to make it work for $2\cdot 3^1 = 6$. – Arthur Mar 08 '15 at 00:49
  • Be careful about the use of $\implies$ symbol. You want to conclude that $3^1>1^3$. But $3^1>1^3\implies 3>1$ doesn't let you conclude that. What you want to say is that $3>1\implies 3^1>1^3$. – Thomas Andrews Mar 08 '15 at 00:58

4 Answers4

3

There is a flaw in the statement you are trying to prove; it is simply false for when $n=3$, since $$ 3^3 \not> 3^3. $$ What you are looking to establish, I suspect, is that $n^3 < 3^n$ for all $n\geq 4$. We can prove this using induction.

Start by noting that $$ 3n^2+3n+1<2(3^n)\tag{1} $$ is true for $n\geq 4$. One can verify $(1)$ using induction or, more cumbersomely, in a direct fashion.

Claim: For $n\geq 4$, $$ n^3 < 3^n. $$

Proof. For $n\geq 4$, let $P(n)$ denote the proposition $$ P(n) : n^3 < 3^n. $$

Base step ($n=4$): Since $4^3=64<81=3^4$, the statement $P(4)$ is true.

Inductive step: Suppose that for some fixed $k\geq 4$, $$ P(k) : k^3 < 3^k $$ holds. It must be shown that $$ P(k+1) : (k+1)^3 < 3^{k+1} $$ follows. Starting with the left-hand side of $P(k+1)$, \begin{align} (k+1)^3 &= k^3+3k^2+3k+1\\[0.5em] &< 3^k+3k^2+3k+1\tag{by $P(k)$}\\[0.5em] &< 3^k+2(3^k)\tag{by $(1)$}\\[0.5em] &= 3(3^k)\\[0.5em] &= 3^{k+1}, \end{align} we end up with the right-hand side of $P(k+1)$. Thus, $P(k+1)$ is also true, and this concludes the inductive step $P(k)\to P(k+1)$.

Thus, by mathematical induction, $P(n)$ is true for all $n\geq 4$. $\blacksquare$

Daniel W. Farlow
  • 22,531
1

Hint

  1. For $n=1,2,3$ it's true:$3^1\geq 1^3$, $3^2\geq 2^3$ and $3^3\geq 3^3$
  2. for some $n\geq 3$, suppose that :$3^k\geq k^3$ for all $k\leq n$ ,so $3^{n-1}\geq (n-1)^3$ but also $3^2\geq 2^3$ hence : $$3^{n+1}=3^{n-1}.3^2\geq 2^3.(n-1)^3=(2(n-1))^3 $$ and now you only need to show that $2(n-1)\geq n+1$ which is true.
Elaqqad
  • 13,725
0

Assume $3^n \gt n^3$. Multiply both sides by $3$ to get:

$$3^{n+1} > 3n^3$$

Now we need to prove $$3n^3 > (n+1)^3 = n^3 + 3n^2 + 3n +1$$

or that $$2n^3 > 3n^2 + 3n +1$$

but for $n>4$ we have $$2n^3 \gt 8n^2 \gt 3n^2 + 3n + 1$$.

JMP
  • 21,771
0

Suppose it is true for some $N$, then

$$3(N+1)^2 + 3(N+1) + 1 =3 N^2 +3 N +1 + 6N + 3 + 1\leq 3^N +6 N + 3 \leq 2\times 3^{N+1}$$

Now, surely, this is realised if

$$12N + 6 \leq 3N^2 + 3 N + 1 \leq 2\times 3^N \implies 6N +3 \leq 3^N$$

Where I have assumed

$$N^2\geq 4N + 5/3$$

Which is true for $N=5$. And $$N^2+2N +1 \geq 5 N +2 N + 1 \geq 4N+5/3$$
So, i can only prove it for $N\geq 5$, but it's a start, no? Then it's enough to show that the original identity holds for 2,3,4 and you are done..

MrFermiMr
  • 176