Proof by Induction: Use generalized PMI to show 2^n > n^2

S

stiffy

New member
Joined
May 24, 2008
Messages
18
Hi there, I am stuck on a homework problem and really need some help.

Use the (generalized) PMI to prove the following:
2^n>n^2 for all n>4

So far all I have been able to do is show p(5) holds and assume P(k) which gives the form 2^(K)>k^2. This is where I am stuck; consequently, I don't know how to show p(k) implies p(k+1). I figured out my other homework problems which mostly involed products and sums. I found those to be easy because, all I needed to do was add or multiply the consequent term (k+1) to the sum or product and then add or multiply to the right hand side (the hypothesis). Then I just had to work out some algebra until I found the K+1 holds. My problem with this problem is that I don't know what to introduce to make it work or how to expand it. simply plugging in k+1 didn't get me anywhere.

Thank you,

Dan
 
Re: Proof by Induction

Show that \(\displaystyle 2 \cdot 2^n > 2n^2 > (n+1)^2\) when \(\displaystyle n>4\).
 
Re: Proof by Induction

I don't understand were I have to arrive with that set up. Is my hypothesis the orginal equation with k+1 plugged into all values? I don't get what changed I have to make to the left and right hand side. I'm lost, sorry. I do see how that makes sense, by I don't see how to bring everything together back to the hypothesis...prolly because, I don't see it.
 
Re: Proof by Induction

Lemma: first show for n>=3, 2^k > 2k+1 (easy, right?)

(k+1)^2 = k^2 + 2k + 1 <* 2^k + 2k + 1 = 2^k + (2k+1) <** 2^k + 2^k = (2)2^k = 2^(k+1)

* is where I used the induction hypothesis.

** is where i used the lemma
 
Re: Proof by Induction

stiffy said:
Hi there, I am stuck on a homework problem and really need some help.

Use the (generalized) PMI to prove the following:
2^n>n^2 for all n>4

So far all I have been able to do is show p(5) holds and assume P(k) which gives the form 2^(K)>k^2. This is where I am stuck; consequently, I don't know how to show p(k) implies p(k+1). I figured out my other homework problems which mostly involed products and sums. I found those to be easy because, all I needed to do was add or multiply the consequent term (k+1) to the sum or product and then add or multiply to the right hand side (the hypothesis). Then I just had to work out some algebra until I found the K+1 holds. My problem with this problem is that I don't know what to introduce to make it work or how to expand it. simply plugging in k+1 didn't get me anywhere.

Thank you,

Dan
Click to expand...

Prove 2^n > n^2, for n > 4

2^(k+1) = 2 2^k > 2(k^2), by inductive assumption

Now we want to prove 2(k^2) > (k + 1)^2

Ready to go:

2(k^2) > (k + 1)^2 if

2(k^2) - (k + 1)^2 > 0 if

2(k^2) - (k^2 + 2k + 1) > 0 if

2(k^2) - k^2 - 2k - 1 > 0 if

k^2 - 2k - 1 > 0 if

k^2 - 2k + 1 - 2 > 0 if

(k - 1)^2 - 2 > 0 if

(k - 1)^2 > 2 if

k - 1 > sqrt(2) if

k > 1 + sqrt(2) = 2.4 (or so)

But k > 4, by assumption. Now work your way back up for the formal proof.
 
Re: Proof by Induction

Stiffy,

Please use a paper and pencil and write down the solutions step-by-step as those were presented to you. Just staring at the screen won't suffice!
 
You must log in or register to reply here.
Top