Question

Show that 2^n > n^2 for all integers n > 4.

Basis: 2^(5) > 5^2 which is true
I.hypothesis: 2^k > (k)^2
I. step: 2^(k+1) > (k+1)^2
(2^k)*2 > (k+1)(k+1)
(2^k)*2 > k^2+2k+1
I'm stuck here. I can't find a way to reduce this, either by relating it to the IH or find a "middle inequality" to prove the induction. Any tips to help me further the question?

Answer 1

we need the k step and the k+1 step... so I usually expand the right as a hint for me to figure out what I need to do with the left

Answer 2

which I did haha. Im stuck at it, thats the thing. If 2^k * 2 > k^2 +2k + 1. There's no way for me to show that 2> 2k + 1 because that would be false in itself. However, when grouped with the 2^k and k^2, it seems that its just unknown

Answer 3

wait a sec.. this could be a different version of the induction... like we do the same find k and k+1 but I think you have to split the 2^(k+1) = 2^k 2^1 = 2(2^k) and then subsitute what 2^k is or what k is crap I need to do this again .... maybe it's in my stackexchange account

Answer 4

i would post on stackexchange but people there are... wingspans a lot of the time

Answer 5

oh yeah...

Answer 6

I remember having to substitute for that 2^k

Answer 7

I can't figure it out still, I got to separating the expression but after that it gets rocky

Answer 8

because that left side of yours is wrong. 2^{k+1} should be 2^k (2)

Answer 9

nughhh even I'm stuck...

Answer 10

I did this problem before... wait let me check my book

Answer 11

wow there's an example sheet that I did a year ago.. I can scan for you if you want

Answer 12

that would be awesome if you dont mind haha

Answer 13

thatd be even too nice o.o

Answer 14

OH! I GET IT NOW! 2k^2 = k^2 + k^2 and then you use pascal's triangle

Answer 15

k I'll scan it

Answer 16

first k^2 is left alone and then you subsitute the second k^2 with 2k and then add 1

Answer 17

wtf is pascale triangle. and wth LOL Im lost you lost me 100% there

Answer 18

2^k = k^2 you use subsitutuion
then
22^k = 2k^2 = k^2 +k^2 skipped a step

Answer 19

2^k = k^2 from that k hypothesis

Answer 20

so you had 2(2^k) using the k hypothesis you subsitute 2^k with k^2 leaving 2(k^2) = 2k^2 which is actually 2k^2 = k^2 +k^2 and then you use pascal's triangle on the second k^2 and add 1

so that's k^2+2k+1 which I got left = right

Answer 21

Ive never learned pascale triangle hahaha, ill check it out. But how did you go from 2(2^k) --> 2(k^2) if 2^k > k^2 at the start ?

Answer 22

what I did a year ago is similar to yours only bigger numbers

Answer 23

o-o 2^k > k^2 was your k hypothesis right?

Answer 24

you subsitutue 2^k with k^2 so you have (2^1)(k^2) = 2k^2 and then you split that into k^2+k^2

Answer 25

if you don't use substitution... you will be stuck and never get it done.. even I did it on my paper check the first problem with the 4

Answer 26

do you see 4^k > k^4 ? I substituted it

Answer 27

nono , I'm not denying what you're saying haha. but if your k hypothesis is 2^k > k^2. How can 2^(K+1) = 2(k^2) if 2^k > k^2

Answer 28

x.x I used to get stuck on that... my adviser told me to subsitute this is a loop question isn't it... first of all the left side of your k+1 is wrong

Answer 29

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

Answer 30

sorry I froze.

Answer 31

how is my k+1 wrong O.o

Answer 32

from the k hypothesis you have 2^k > k^2 so you need to exchange 2^k with k^2 ... the way you split it up is wrong

Answer 33

it's similar to exponentials... e^(x+1) is the same as e^x(e^1)

Answer 34

so 2^(k+1) is really 2^k(2^1) = 2^k(2) and I did that too on my paper

Answer 35

thats what I said O.o 2^(k+1) is the same as (2^k)(2) haha

Answer 36

not in the original post when you asked the question

Answer 37

whoops tryping error then! :) but you then said 3k * 3 = 3k^3 right?

Answer 38

in your paper that is

Answer 39

O_____________O! I'm focusing on the first question

Answer 40

WHOOPS wrong one lol sorry

Answer 41

when i splitted it up again I exchanged 4^k with k^4 using the k hypothesis leave you with 4k^4 that is actually = k^4+k^4+k^4+k^4 then you add 1 at the end and use pascal's triangle to figure out the 2-4th k^4s except yours should be easy

Answer 42

same idea though you said 4^k * (4) is equivalent to 4k^4

Answer 43

I mean you exchanged an exponent with a base, to me thats defying the law of math o.o

Answer 44

tell that to my adviser. he taught me how to do it

Answer 45

LOL im sorry its just weird to me, i didnt know you could do it. Im not trying to say anything bad, im far from having a phd in math or anything. It just seems... odd that 4^k * (4) = 4k^4

Answer 46

UGH! YOu just exchange 4^k with k^4 using the k hypothesis!!!

Answer 47

Its okay I just verified it using numbers, its true, but its just weird lol cause we have an inequality. if 4^k = k^4 in k I would do it but we have greater then, hence why I felt weird about doing it. thats all haha