Intereting Posts

Do the infinite series converge
Arbitrarily discarding/cancelling Radians units when plugging angular speed into linear speed formula?
Enumerating all subgroups of the symmetric group
Sequence of functions: Convergence
Book/tutorial recommendations: acquiring math-oriented reading proficiency in German
How to compute the residue of a complex function with essential singularity
How to show that every Boolean ring is commutative?
Why does every countable limit ordinal have cofinality $\omega$?
What are “Lazard” sheaves?
Connected Implies Path (Polygonally) Connected
Proving an equality involving compositions of an integer
For every prime of the form $2^{4n}+1$, 7 is a primitive root.
Idealizer of one-sided ideal
Can we prove the open mapping theorem using the maximum modulus principle?
Every polynomial with real coefficients is the sum of cubes of three polynomials

How do I prove that $3^n > n^2$ with mathematical induction? I thought I had the correct answer but my teacher says its wrong.

I let $n=1$ for the initial case and it works. I then assumed $n=k$ works and went onto the $n=k+1$ case, but after that it goes a little awry. Thanks in advance!

- Prove by induction $ \sin x + \sin 2x + … + \sin nx = \frac {\sin (\frac {n + 1} {2} x)} {\sin \frac{x}{2}} \sin \frac{nx}{2} $
- Proving $\sum\limits_{k=1}^{n}{\frac{1}{\sqrt{k}}\ge\sqrt{n}}$ with induction
- Proof writing: how to write a clear induction proof?
- Is it a new type of induction? (Infinitesimal induction) Is this even true?
- In-Depth Explanation of How to Do Mathematical Induction Over the Set $\mathbb{R}$ of All Real Numbers?
- Proving the geometric sum formula by induction

- Induction proof. Explain in detail why it’s incorrect
- $n! \leq \left( \frac{n+1}{2} \right)^n$ via induction
- Proving $2^n\leq 2^{n+1}-2^{n-1}-1$ for all $n\geq 1$ by induction
- Why doesn't induction extend to infinity? (re: Fourier series)
- How to prove a formula for the sum of powers of $2$ by induction?
- Proving $\sum_{k=1}^n\frac1{\sqrt k}<2\sqrt n$ by induction
- Proving that $1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\cdots+\frac{1}{2n-1}-\frac{1}{2n}=\frac{1}{n+1}+\frac{1}{n+2}+\cdots+\frac{1}{2n}$
- Prove by mathematical induction that: $\forall n \in \mathbb{N}: 3^{n} > n^{3}$
- Proof by Induction for inequality, $\sum_{k=1}^nk^{-2}\lt2-(1/n)$
- Induction to prove $2n + 3 < 2^n$

The base case is just noticing $3^1>1^2$.

The inductive step:

Suppose $3^n>n^2$ we want to prove $3^{n+1}=3^n+3^n+3^n>1+2n+n^2=(n+1)^2$

This follows from the following:

$3^n\geq 1$

$3^n\geq 2n$ (you may have a go at this with another induction)

$3^n> n^2$ (inductive step)

I’ll outline a more or less self-contained proof. However, it may be worth observing that your own problem follows as a trivial conclusion of proving that $3^n\geq n^3$ for all $n\geq 1$. Here is an answer to that problem if you want to check it out.

To prove that $3^n>n^2$ for all $n\geq 1$ using induction, it will be useful to use **two** base cases at the beginning (this has already been referenced in one or two previous comments). The reason for this will become clear at the end.

Let $S(n)$ denote the following for $n\geq 1$ where $n\in\mathbb{N}$:

$$

S(n) : 3^n>n^2.

$$

**Base step ($n=1,2$):** $S(1)$ says that $3^1=3>1=1^2$, and this is true. Now, $S(2)$ says that $3^2=9>4=2^2$, and this is also true.

**Inductive step:** Fix some $k\geq 2$ and assume that $S(k)$ is true where

$$

S(k) : 3^k>k^2.

$$

To be shown is that $S(k+1)$ follows where

$$

S(k+1) : 3^{k+1} > (k+1)^2.

$$

Beginning with the left-hand side of $S(k+1)$,

\begin{align}

3^{k+1} &= 3\cdot 3^k\tag{by definition}\\[0.5em]

&> 3\cdot k^2\tag{by $S(k)$, the ind. hyp.}\\[0.5em]

&> k^2+2k+1\tag{since $k\geq 2$; see $(\dagger)$}\\[0.5em]

&= (k+1)^2,

\end{align}

we end up at the right-hand of $S(k+1)$, completing the inductive step.

By mathematical induction, the statement $S(n)$ is true for all $n\geq 1$. $\blacksquare$

**$(\dagger)$:** When $k\geq 2$, how can we claim that $3k^2>k^2+2k+1$? Notice that

$$

3k^2>k^2+2k+1 \Longleftrightarrow 2k^2-2k-1 > 0 \Longleftrightarrow k(2k-2)-1>0,

$$

and this is obviously true for $k\geq 2$, but it is not true when $k=1$, and this explains why we needed two base cases at the beginning.

We can show the inequality directly for $n=1$ and $n=2$.

Suppose $3^n>n^2$ as the inductive hypothesis.

For $n \geq 2$, $2.n^2 > 2n + 1$. Can you see why?

Then $3^{n+1} = 3.3^n > 3.n^2 = n^2 + 2.n^2 > n^2+2n+1 = (n+1)^2$.

The first inequality is via the inductive hypothesis, and the second inequality is via the inequality above.

You seem to have the principle correct, so the issue is one of application. There are probably simpler methods than this, but here is one way.

Show that it works for $n \in \{1, 2, 3\}$:

$$

\begin{align}

3^1 = 3 &> 1^2 = 1\quad \checkmark\\

3^2 = 9 &> 2^2 = 4\quad \checkmark\\

3^3 = 27 &> 3^2 = 9\quad \checkmark

\end{align}

$$

Now, let’s assume $3^n > n^2$. We need to prove that $3^{n+1} > \left(n+1\right)^2$.

$$

\begin{align}

3^{n+1} = 3 \times 3^n &= 3^n + 3^n + 3^n\quad&(1)\\

(n+1)^2 &= n^2 + 2n + 1\quad&(2)\\

\end{align}

$$

Looking at how the columns line up on the right side of (1) and (2), we can show that all corresponding elements of the top row are greater than those in the bottom row. In the first column, the top row is larger than the bottom row, we assumed it as part of the inductive step. The second column is true as $n^2 > 2n$ for all $n > 2$. So if $3^n > n^2$ via the induction step, it is certainly greater than $2n$. This is why we proved the individual cases up to 3 above. If your teacher is strict, you may have to prove this as a lemma using induction as well. The last column is true for all $n > 0$, and we started our induction step at 3. QED.

Just to be complete, we can show $n^2 > 2n$ for $n \geq 3$.

$$

3^2 = 9 > 2\times 3 = 6\quad \checkmark

$$

Assume $n^2 > 2n$. Show $(n+1)^2 > 2(n+1)$.

$$

\begin{align}

(n+1)^2 = &n^2 +& 2n + &1\\

2(n+1) = &&2n + &2

\end{align}

$$

The $2n$ cancels, and we have to show that $n^2 + 1 > 2$, or $n^2 > 1$, which is trivial for $n > 3$.

To get from $3^n$ to $3^{n+1}$ you multiply by $3$. To get from $n^2$ to $(n+1)^2$, you multiply by $(\frac {n+1} n)^2$. Clearly $(\frac {n+1} n)^2$ will eventually by strictly smaller than $3$, and therefore past that point, the inequality $3^n>n^2$, if it’s ever true, will be true forever afterwards.

Now, $(\frac {n+1} n)^2=(1+\frac 1 n)^2$ is a decreasing sequence which tends towards $1$, and some computation shows that for $n=2$ it is already below $3$. So we just have to check $3^2>2^2$, which is indeed true.

- Riemann zeta function and the volume of the unit $n$-ball
- Identifying 2 poisoned wines out of 2^n wines
- $\{m \alpha, m \in \mathbb Z\}$is dense in $$ for $\alpha$ irrational
- Limit of $a_{k+1}=\dfrac{a_k+b_k}{2}$, $b_{k+1}=\sqrt{a_kb_k}$?
- Rating system incorporating experience
- Find equation of ellipse given two tangent lines at given points and a point on ellipse
- Is Steinhaus theorem ever used in topological groups?
- Find continuous functions such that $f(x+y)+f(x-y)=2$
- Why would some elementary number theory notes exclude 0|0?
- The Area of an Irregular Hexagon
- Why is $PGL(2,4)$ isomorphic to $A_5$
- How to prove that $\frac{\zeta(2) }{2}+\frac{\zeta (4)}{2^3}+\frac{\zeta (6)}{2^5}+\frac{\zeta (8)}{2^7}+\cdots=1$?
- Examples of problems that are easier in the infinite case than in the finite case.
- Surprise exam paradox?
- How to prove that $\sqrt 2 + \sqrt 4$ is irrational?