Question

Please help prove
4^n >n^2 for all non-negative integers n

Answer 1

Ignore basic step and hypothesis one, I got stuck at the last step only
\[4^{n+1}>(n+1)^2\]

Answer 2

I have class now. Please, leave your guidance here. Thanks in advance ;)

Answer 3

I was thinking take the log of both sides
n log4 > 2 log n
(1/2) log4 > (1/n) log n
log 2 > log( n^(1/n) )
2 > n^(1/n)

we know 4^n > n^2 for n=0, n=1...
the limit as n->infinity of n^(1/n) is 1

Answer 4

inductive reasoning:
base cases: true for n=0,1,2

assume true for n≥2
4^n > n^2

then
4 * 4^n > 4n^2
4^(n+1) > 4 n^2

aside: use induction to show 4 n^2 > (n+1)^2 for n>=2
base case:
4*2^2 = 16 > 3^2
16>9
true

for n+1:
4 (n+1)^2 > ? ( (n+1) +1)^2
4 n^2 + 8n + 4 > ? n^2 +4n + 4
3 n^2 + 4n > ? 0
true for all n≥2, therefore
4 n^2 > (n+1)^2 for n>=2

we use this result to write
4^(n+1) > 4 n^2 > (n+1)^2
4^(n+1) > (n+1)^2
i.e. true for the n+1 instance, given it's true for the nth instance.

Answer 5

Can I go on this way?
Basic step: P(1) := \(4^1> 1^2 \\4>1\)
P(1) is true
Inductive steps:
Assume P(n) is true
P(n) := \(4^n > n^2\)
We need to prove P(n) -> P(n+1)
P(n+1) := \(4^{n+1} > (n+1)^2\)
the left hand side: \(4^{n+1}= 4^n*4=4^n+4^n+4^n+4^n\)
the right hand side: \((n+1)^2 = n^2+2n+1 = n^2+n+n+1\)
I have: \(4^n > n^2~~~~~~~~~ \text {(hypothesis step)}\)
\(4^n >n ~~~ \forall n>0 \) \(\color{red}{\text {do I have to prove it??}}\)
\(4^n>n\)
\(4^n >1 \)
--------------------------------------------------------------
\(4*4^n > n^2 +2n +1\\4^{n+1}>(n+1)^2\)

Answer 6

you could just make a short note:
given n>1, multiply both sides by n:
n^2 > n
therefore 4^n > n^2 implies 4^n > n for n>1

Answer 7

Thank you, I got it. :)