5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user 170039 Jul 25 '16 at 13:37
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Tars Nolan Jul 25 '16 at 14:14
  • $\begingroup$ 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$. $\endgroup$ – Zain Patel Jul 25 '16 at 14:15
  • $\begingroup$ Yes i know but i ask if it is possible for $3n^{2}$ to be eaqual to $(n+1)^{2}$? $\endgroup$ – Tars Nolan Jul 25 '16 at 14:36
  • $\begingroup$ 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$. $\endgroup$ – Zain Patel Jul 25 '16 at 14:39
  • $\begingroup$ @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.$ $\endgroup$ – DanielWainfleet Jul 28 '16 at 4:01
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "$n^2 \geq 2n, n\geq 1$". Hmm... $1^2 \not\geq 2(1)$. :-P $\endgroup$ – Zain Patel Jul 25 '16 at 13:57
  • $\begingroup$ edited/corrected $\endgroup$ – miniparser Jul 25 '16 at 14:03
  • $\begingroup$ worth noting that the other answers also begin at $2$. $\endgroup$ – miniparser Jul 25 '16 at 19:06
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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