help: induction (1 Viewer)

[tooheyz]

hey guys, im having trouble with this one question, can any of you help out?

thanks

prove, by induction that for all positive integers n

2^n >= (n+1)

[ two to the power of n is greater than or equal to (n+1) ]

i did S(1) blah blah

but for S(n+1)

my LHS = 2^ (n+1) = 2.2^n = 2 (n+1)
RHS = [(n+1) +1] = (n+2)

which doesnt equal... what am i doing wrong?

many thanks

 

[wogboy]

but for S(n+1)

my LHS = 2^ (n+1) = 2.2^n = 2 (n+1)
RHS = [(n+1) +1] = (n+2)

Firstly your aim isn't to make the LHS = RHS, rather it is LHS >= RHS. And how 2.2^n = 2 (n+1) is beyond me

---------------------------------------------

Assume 2^k >= k + 1

We need to prove 2^(k+1) >= k + 2
i.e. 2^k >= k/2 + 1

but we've assumed 2^k >= k + 1,
and we know k + 1 >= k/2 + 1 (for k >= 0)
so 2^k >= k/2 + 1
so 2^(k+1) >= k + 2

therefore the proposition is true by induction.

 

[KeypadSDM]

Originally posted by wogboy
therefore the proposition is true by induction.

I think you mean Q.E.D.

 

[tooheyz]

Originally posted by wogboy


and we know k + 1 >= k/2 + 1 (for k >= 0)

eeerr, how did u get that?

 

[freaking_out]

Originally posted by tooheyz
eeerr, how did u get that?

well think abt. it- sub in values of k (which are above 0) and u'll c how its just a basic thing.

 

[Heinz]

Originally posted by freaking_out
well think abt. it- sub in values of k (which are above 0) and u'll c how its just a basic thing.

in other words, any positive integer plus one will always be greater than half of that positive integer plus one. Its pretty logical. btw, havent you finished school tooheyz? unless you like doing maths for fun or this is for uni?

 

[freaking_out]

Originally posted by Heinz
in other words, any positive integer plus one will always be greater than half of that positive integer plus one. Its pretty logical. btw, havent you finished school tooheyz? unless you like doing maths for fun or this is for uni?

she's doing it for FUN! (NOT!)

 

[Grey Council]

Firstly your aim isn't to make the LHS = RHS, rather it is LHS >= RHS. And how 2.2^n = 2 (n+1) is beyond me

He/she used assumption. I think. hehe, lets see, i'll use tooheyz method:
RTP
2^n >= (n+1)

for n=k+1
LHS = 2^(k+1) = 2.2^k = 2 (k+1) (ie from assumption 2^k >= k+1, therefore if LHS greater than RHS with k+1, then it will be true for 2^k)
RHS = [(k+1) +1] = (k+2)
on the LHS:
2(k+1) = 2k + 2
RHS:
k+2

now tell me, is (2k+2) more than or equal to (k+2) or not? LOL, tooheyz, you just had to do that one extra step. lol

and tell me if you don't understand anything. I'm half asleep, hehe, its 7am, i've prolly made some typing mistake somewhere.

 

[tooheyz]

man, bloody hell. im gonna kill this idiot!
i was told by someone that the answers HAD TO EQUAL

and stupid me, i believed him

thanks for everything guys!

Originally posted by Grey Council
He/she used assumption. I think. hehe, lets see, i'll use tooheyz method:
RTP
2^n >= (n+1)

for n=k+1
LHS = 2^(k+1) = 2.2^k = 2 (k+1) (ie from assumption 2^k >= k+1, therefore if LHS greater than RHS with k+1, then it will be true for 2^k)
RHS = [(k+1) +1] = (k+2)
on the LHS:
2(k+1) = 2k + 2
RHS:
k+2

now tell me, is (2k+2) more than or equal to (k+2) or not? LOL, tooheyz, you just had to do that one extra step. lol

and tell me if you don't understand anything. I'm half asleep, hehe, its 7am, i've prolly made some typing mistake somewhere.

and yeah, thats all my working out!

 

[KeypadSDM]

Originally posted by tooheyz
eeerr, how did u get that?

k>=0
k/2 >= 0
k >= k/2
k + 1 >= k/2 + 1

 

[zxl]

LHS= 2^(k+1)
= 2^k * 2^1 = 2 * 2^k
>= 2 (k + 1) (using assumption)
= 2k + 2
> k + 2 (2k > k, duh..)
= (k + 1) + 1
therefore LHS > RHS for all positive k
and blah blah blah...

 

[Grey Council]

hah! another actuary has joined these forums. actuary wanna be anyway. Welcome zxl. I'm looking forward to your solutions to problems. hehe, i wanna be an actuary too. ^_^

 

[grimreaper]

Originally posted by Grey Council
hah! another actuary has joined these forums. actuary wanna be anyway. Welcome zxl. I'm looking forward to your solutions to problems. hehe, i wanna be an actuary too. ^_^

Haha wow I'm thinkin of doin actuarial studies too (at Macquarie)