Prove by induction (discrete math's)

[vvvidenov]

Homework Statement

Prove by induction that
n!> 2^n for n\geq4

Homework Equations

solved example:
P(n): 2^n>1+3n let n\geq4
(base): n=4 2^4=16 > 13=1+12=1+(3)(4)

(implication): if for n=k: P(k): 2^k>1+3k, for k\geq4

consider for n=(k+1):

2^(k+1)=2^k*2^1=2^k(1+1)=2^k+2^k >(1+3k) + (1+3k) for k\geq4
>1+3k+3k
\geq1+3k+12 > 1+3k+3
= 1+3(k+1)
so P(k) => P(k+1)

The Attempt at a Solution

(Base) n=k
P(k): k!>2^k

(Implication) show P(k)=> P(k+1)

Consider: n=k+1

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

(k+1)! = (k+1)k!> (k+1)*2^k

Please help if you can. I am confused. Thanx.

 

[sutupidmath]

assume that the proposition holds for n=k, that is

k!>2^k----------------(IH) we want to show that it also holds for n=k+1 ?

(k+1)!=(k+1)k!=>(IH) (k+1)k!>(k+1)2^k>2*2^k=2^{k+1}

since k+1>2 for k>=4.

 

[vvvidenov]

What (IH) means?. I am sorry but English is a second language to me, and I did study most of my math in Europe many years ago.
I am back to school now.
Thank you.

 

[HallsofIvy]

"IH" means the "induction hypothesis":that the statement is true for n= k which you then use to show that it is true for n= k+1.

Also, the "base" case refers to showing that the statement is true for the beginning number, which, here, is n= 4. Is 4!> 2⁴?

I would NOT start by asserting that "(k+1)! > 2^(k+1)". That is what you want to prove. Better is to start:

(k+1)!= (k+1)(k!)> (k+1)(2^k), where I have used the induction hypothesis: k!> 2^k. Can you show that (k+1)(2^k is greater than or equal to 2^k+1? Remember that k is at least 4.

 

[vvvidenov]

I am sorry, thanks for the note. I know that I have to start first with the proof in base part, I just skip it in a hurry.

Here is: let n=4
n!>2^n
4!>2^4
24>16

(base) n=k
k!>2^(k+1)

consider for n=k+1

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

I don't know how to show it. Please help. Can you show that (k+1)(2k is greater than or equal to 2k+1? Remember that k is at least 4.

 

[HallsofIvy]

Could you show that 3(2^k)> 2^k+1?

How large is k+1?

 

[vvvidenov]

I am not sure , but I will try.
6^k > 2^k*2

I don't think I can finish this problem. I asked in class similar problem ,but this professor is happy to make us more confused, he doesn't explain well at all. I also don't think that other kids in the class get it. I just don't get it, sorry.

 

[vvvidenov]

How large is k+1?
n=k=4
k+1=5
Then what?

 

[HallsofIvy]

I am not sure , but I will try.
6^k > 2^k*2

I don't think I can finish this problem. I asked in class similar problem ,but this professor is happy to make us more confused, he doesn't explain well at all. I also don't think that other kids in the class get it. I just don't get it, sorry.

Well, the important thing is to be able to blame your professor isn't it? That way you don't have to take responsibility for your own education.

Who are you going to blame for the fact that you think 3*2^k is equal to 6^k?

 

[vvvidenov]

Didn't you make a mistake under presure or in a hurry to get many thinks done. I mention that I am almost 50 years old and I am back to school.
I it is diffucult for me. I can get this problem done even without your help.

I don't blame anybody. But similar example was given and you have no idea what kind of people are teaching around the country. Excusme, but a good mathematicians don't make good teachers.

I was confised from the different form given in the example.
Thank you anyway. Please forget about this problem and delete it.