How to prove that $4^n>n^2$ using induction...

Question

today I've encountered a question like the following; $$\text{Prove that }4^n>n^2\text{ using induction.}$$ My Attempts:

I have realised that this works for $P(1)$, my next attempt was $p(n)\implies p(n+1)$....(1)

I have tried to multiply both sides with a $4$ which gave $4^{n+1}>4n^2$ I have tried to turn it out like $4>1^2$ and that gave me $4^{n+1}>n^2\cdot1^2$.....(2)

After that pointless attempt I've added $2n+1$ to both sides but I couldn't figure out still what $2n$ goes to in the left side...(3)

What are your suggestions?

With the real question being the first one, is there any other way to prove this numerically? (Perhaps in a more entertaining way?:))

Okay. It is true for $P(1)$ and $P(n+1): 2^n\cdot2>2n$. How can I get rid of the $2$ at the right side? (Thanks for the advice by the way:)) — Deniz Tuna Yalçın, Oct 15 '17 at 09:46
$$\begin{align} 4^n &> n^2 \ \iff 2^{2\times n} &> n^{2\times 1} \ \iff 2^n &> n \ \iff 2^n &> \log_2 k \end{align}$$ for which $k = 2^n$, which is true. The reason this is a comment is because I didn't prove this using induction — Mr Pie, Oct 15 '17 at 09:48
You could've put this as an answer too, another part of my question was without induction. Thank you:) — Deniz Tuna Yalçın, Oct 15 '17 at 09:56
Hint: $$\frac{(n+1)^2}{n^2} \leqslant 4$$ for $n \geqslant 1$. — πr8, Oct 15 '17 at 09:59

Raffaele · Accepted Answer · 2017-10-15T11:32:22.717

3

Numerically is not a proof.

Induction works in this way

It is true for $n=1$
Suppose that is is true for $n>1$, prove it for $n+1$
It is true for any $n\in\mathbb{N}$.

proof

actually $4^1> 1^2$
(I.H.) if $4^n>n^2$ for $n>1$ consider that $4^{n+1}=4\cdot 4^n$. Now use the Inductive Hypothesis (I.H.)

$4\cdot 4^n > 4\cdot n^2 =2^2 \cdot n^2=(2n)^2>(n+1)^2$ as $n>1$

proved, so

For any $n\in \mathbb{N}$ we have $4^n>n^2$

QED $$ . $$

To say the truth $4^n > n^{1000}$ for $n>6312$

Indeed induction can start from any $n$, but this is another story

edited Oct 15 '17 at 11:32

answered Oct 15 '17 at 09:55

Raffaele

26,371

Technically your proof is invalid because $(2n)^2 > (n+1)^2$ fails for $n = 1$. You needed to separate $n = 1$ and $n = 2$ into separate cases. – orlp Oct 15 '17 at 10:29
@orlp It is understood that AFTER having considered $n=1$, the rest of the proof is for $n>1$ anyway I edited my proof so please delete your downvote – Raffaele Oct 15 '17 at 11:31
Not necessarily. Your (pre-edit) induction hypothesis assumes $n=1$ to prove that it holds for $n=2$, however in your example this proof fails. In the very first step you very much have $n = 1$, because you use $n$ to prove $n+1$. If your proof instead uses $n-1$ to prove $n$, then you can start from $n = 2$. – orlp Oct 15 '17 at 11:33

score 1 · Answer 2 · answered Oct 15 '17 at 10:32

1

At the point where you have $4^{n+1}>4n^2$ (from the induction hypothesis) you can try and prove that $$ 4n^2\ge(n+1)^2 $$

This is equivalent to $$ 3n^2-2n-1\ge0 $$ or $(3n+1)(n-1)\ge0$. Is this true?

answered Oct 15 '17 at 10:32

egreg

238,574

It is true for $n\geq1$, and we already know that it is because we have begun the proof with $n=1$ and moved forward. (Is that right?) Thank you ::)) – Deniz Tuna Yalçın Oct 15 '17 at 11:55
@DenizTunaYalçın Yes: we are assuming $n\ge1$. – egreg Oct 15 '17 at 12:46

How to prove that $4^n>n^2$ using induction...

2 Answers2

Linked