4
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Start the induction with $n=3$, and check the $n=1,2$ cases separately. $\endgroup$ – AMPerrine Mar 8 '15 at 0:47
  • $\begingroup$ 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$. $\endgroup$ – Arthur Mar 8 '15 at 0:49
  • $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Mar 8 '15 at 0:58
2
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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.
$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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