5

Prove this inequality $3^{n}\geq n^{2}$ for $n\geq 1$ with mathematical induction.

Base step: When $n=1$

$3^{1}\geq1^{2}$, statement is true.

Inductive step: We need to prove that this statement $3^{n+1}\geq (n+1)^{2}$ is true.

So, to get the left side of this statement is easy. We can get it by multiplying $3^{n}\geq n^{2}$ with $3$.

After this step we have $3^{n+1}\geq 3n^{2}$.

What we now have to get is the right side and we can transform it like this:

$3n^{2}= (n^{2}+2n+1)+(2n^{2}-2n-1)$ which is same as

$(n+1)^{2}+(2n^{2}-2n-1)$.

So now we have $(n+1)^{2}$ and $(2n^{2}-2n-1)$ and my question is how should i use this to prove inequality?

Tars Nolan
  • 387
  • Where you wrote $\Leftrightarrow$, there should be $=$. For the question regarding $2n^2-2n-1$, observe that, $$2n^2-2n-1=(n^2-2)+(n^2-2n+1)=(n^2-2)+(n-1)^2$$Can you take it from here? –  Jul 25 '16 at 13:37

5 Answers5

2

Hint: $3n^2-(n+1)^2=2n^2-2n-1>0$ for all $n>1$.

Kushal Bhuyan
  • 7,110
2

Essentially, you want to show that $$3n^2 > (n+1)^2$$ which is not so hard since $$3n^2 - (n^2 + 2n + 1) > 0 \iff 2n^2 - 2n-1 > 0$$

But $2n^2 - 2n - 1 = 2(n^2 -n) - 1 = (n^2-2) + (n^2 - 2n+1) =(n^2 -2) + (n-1)^2$, so that we have for all $n \geq 2$ that $2n^2 - 2n - 1 \geq 0$ since $(n-1)^2$ is always $\geq 0$ and $n^2 - 2$ is $\geq 0$ when $n\geq 2$. Then this means that $$3n^2 \geq (n+1)^2$$ for all $n\geq 2$. And hence:

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

and we are done.

This is a very common tactic in inequality induction proofs, you have the inequality arising from your hypothesis; you then multiply both sides by something to get one side of the inequality in the required inductive form (say $a >b$, where $a$ is the required form) and then prove an inequality chain $b > \cdots > d$ where $d$ is the required form.

Zain Patel
  • 16,802
  • I understand tactic but i wonder if it is right to use this statement $3n^{2}≥(n+1)^{2}$? Because we assume that $3n^{2}$ is smaller then $3^{n+1}$ is it possible that $3n^{2}$ and $(n+1)^{2}$ can be equal? – Tars Nolan Jul 25 '16 at 14:14
  • The statement means "greater than OR equal to". So, for example, it's more than okay to write $2 \geq 1$ even if $2 \neq 1$. – Zain Patel Jul 25 '16 at 14:15
  • Yes i know but i ask if it is possible for $3n^{2}$ to be eaqual to $(n+1)^{2}$? – Tars Nolan Jul 25 '16 at 14:36
  • Not in the naturals; they're only equal when $n = \frac{1 \pm \sqrt{3}}{2}$, so they're never equal when $n$ is an integer, and $3n^2$ is greater when $n \geq 2$. – Zain Patel Jul 25 '16 at 14:39
  • @Tars Nolan. For $n\geq 2$ we have $3n^2>(n+1)^2\iff$ $ 3n^2\geq n^2+2n+1\iff $ $ 2n(n-1)>1 $ which holds, as $ n\geq 2\implies$ $ n-1\geq 1 \implies$ $ n(n-1)\geq 2\cdot 1=2>1.$ – DanielWainfleet Jul 28 '16 at 04:01
2

$3^n\ge n^2, n\ge2$

$3^{n+1}=3^n+3^n+3^n\ge n^2+n^2+n^2\ge n^2+2n+1=(n+1)^2$

This uses the fact that $n^2\ge 2n,n\ge 2$ which can be shown via induction as well and obviously $n^2\ge1$ for all $n\ge 2$. The case for $1$ can be shown and then use $2$ as the base case.

miniparser
  • 1,197
2

Let $S(n)$ be the statement: $3^{n}\geq{n^{2}}$; $n\geq{1}$

Basis step: $S(1)$:

LHS: $3^{(1)}=3$

RHS: $(1)^{2}=1$

$\hspace{77.5 mm}$ LHS $\geq$ RHS $\hspace{1 mm}$ (verified.)

Inductive step:

Assume $S(k)$ is true, i.e. assume that $3^{k}\geq{k^{2}}$; $k\geq{1}$

$\hspace{59 mm}\Rightarrow 3\bullet{3^{k}}\geq{3\bullet{k^{2}}}$

$S(k+1)$: $3^{k+1}$

$\hspace{12.5 mm}=3\bullet{3^{k}}$

$\hspace{11 mm}\Rightarrow 3\bullet{3^{k}}>3\bullet{k^{2}}$

$\hspace{11 mm}\Rightarrow 3^{k}+3^{k}+3^{k}>k^{2}+k^{2}+k^{2}$

$\hspace{40 mm}>k^{2}+2k+1=(k+1)^{2}$

So, $S(k+1)$ is true whenever $S(k)$ is true.

Therefore, $3^{n}\geq{n^{2}}$; $n\geq{1}$.

Tazwar
  • 671
1

Hint: $3 > 1.5^2 \ge (1+\frac1n)^2 = (n+1)^2/n^2$ whenever $n\ge 2$.

Erick Wong
  • 25,198
  • 3
  • 37
  • 91