An induction question (inequality). :) (1 Viewer)

[~shinigami~]

If someone would be so kind as to show me how to do this question, I would greatly appreciate it. I get stuck in step 3.

Prove by mathematical induction that n! > 2ⁿ for all positive intergers where n ≥ 4.

Step 1

Let n = 4

LHS = 24

RHS = 16

LHS > RHS

∴ True for n = 4

Step 2

Assume true for n = k

i.e. k! > 2^k

Step 3

Prove true for n = k+1

i.e. (k+1)! > 2^k+1

This is most important part which is where I get stuck. Hopefully someone can do it. Thank you in advance.

 

[SoulSearcher]

In other words,
(k+1)! - 2^k+1 > 0
LHS = (k+1)! - 2^k+1
= (k+1)k! - 2*2^k
> (k+1)2^k - 2*2^k, using induction hypothesis
= k*2^k + 2^k - 2*2^k
= k*2^k - 2^k
= (k-1)2^k
> 0, since k > 4 and 2^k is positive for all values of k > 4
Therefore (k+1)! - 2^k+1 > 0
and thus (k+1)! > 2^k+1

And so forth.

 

[Trebla]

LHS = (k + 1)!
= k!(k + 1)
> 2^k(k + 1) by assumption
since k ≥ 4, the minimum value of 2^k(k + 1) is 2^k.5. Now this is greater than 2^k.2, for all values of integer k ≥ 4 hence
> 2^k.2
= 2^k+1

 

[~shinigami~]

In other words,
(k+1)! - 2^k+1 > 0
LHS = (k+1)! - 2^k+1
= (k+1)k! - 2*2^k
> (k+1)2^k - 2*2^k, using induction hypothesis
= k*2^k + 2^k - 2*2^k
= k*2^k - 2^k
= (k-1)2^k
> 0, since k > 4 and 2^k is positive for all values of k > 4
Therefore (k+1)! - 2^k+1 > 0
and thus (k+1)! > 2^k+1

And so forth.

Man, I was scratching my head for ages on that one.


Thanks SoulSearcher. You're a champ!

LHS = (k + 1)!
= k!(k + 1)
> 2^k(k + 1) by assumption
since k ≥ 4, the minimum value of 2^k(k + 1) is 2^k.5. Now this is greater than 2^k.2, hence
> 2^k.2
= 2^k+1

Thank you as well, Trebla.

 

[pyrodude1031]

i personally reckon.. the LHS - RHS method is not very appropriate .. because .. using such approach .. is kind of assuming the answer is true already ... since LHS is > RHS ... then LHS-RHS will of cos be > 0 . so I reccomend the second method(Shinigami's) ... the one in which u prove from LHS ... and eventually get >RHS.

Pyrodude1031

 

[Raginsheep]

Theres a slight difference. Proving LHS - RHS > 0 is equviliant to proving LHS > RHS. You don't actually assume that LHS is greater than RHS.

For this question, second method is much shorter however.

 

[Trebla]

LHS = (k + 1)!
= k!(k + 1)
> 2^k(k + 1) by assumption
since k ≥ 4, the minimum value of 2^k(k + 1) is 2^k.5. Now this is greater than 2^k.2, for all values of integer k ≥ 4 hence
> 2^k.2
= 2^k+1

Also, with this method it is possible (as well as very easy) to get away with fudging it for those who don't understand it very well, provided the reasoning makes sense. So, you can easily bluff your way through the proof without going through the logical process (which in a way can be good thing). I'm guessing that may be the reason why induction inequality questions are quite rare in HSC exams. Personally, I prefer this method because it shows a greater understanding of inequalities (which is very useful in Extension 2 inequalities).

 

[pLuvia]

Yes, you will commonly see these type of induction questions in HSC MX2 exams and can be quite annoying sometimes. But once you know how to do it, it's quite easy

 

[Forbidden.]

Yes, you will commonly see these type of induction questions in HSC MX2 exams and can be quite annoying sometimes. But once you know how to do it, it's quite easy

I dont do Ext 2. but how much more induction madness will I have to deal with throughout HSC Maths Ext. 1 ?

Also, my first HSC Ext 1 Assessment was a taste what will come later, furthermore using second derivative is impractical to me in further curve sketching.

 

[pLuvia]

These type of induction aren't common (from my experience) but usually the types of induction are like proving divisibility, and those other inductions where you prove this is equal to that for MX1.

MX2 isn't that much different but just that you have to approach the induction differently like here

 

[~shinigami~]

These type of induction aren't common (from my experience) but usually the types of induction are like proving divisibility, and those other inductions where you prove this is equal to that for MX1.

MX2 isn't that much different but just that you have to approach the induction differently like here

Is there more to your post? For some reason I feel like there is somethign cut out after "...here...".

 

[Raginsheep]

You probably should learn both approaches since sometimes one approach is considerably easier than the other.

 

[~shinigami~]

You probably should learn both approaches since sometimes one approach is considerably easier than the other.

Thanks for the advice Raginsheep.

I don't know if it's just me but sometimes, Inequality induction feels "cheap" if you know what I mean.

 

[Forbidden.]

Sometimes I give myself a pat on the back for not studying Extension 2, not only do you have to stay back at random times during the week for it (i.e lunch time, free period), most of the students fail.

 

[Raginsheep]

Umm........wtf? I didn't stay back at random times, and didn't fail.

If your too stupid to do Ext2, don't just continue to moan about it....