# Prove by induction (discrete math's)

1. Nov 4, 2008

### vvvidenov

1. The problem statement, all variables and given/known data

Prove by induction that
n!> 2^n for n$$\geq$$4

2. Relevant equations

solved example:
P(n): 2^n>1+3n let n$$\geq$$4
(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$$\geq$$4

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$$\geq$$4
>1+3k+3k
$$\geq$$1+3k+12 > 1+3k+3
= 1+3(k+1)
so P(k) => P(k+1)

3. 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

2. Nov 4, 2008

### 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.

3. Nov 5, 2008

### 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.

Last edited: Nov 5, 2008
4. Nov 5, 2008

### HallsofIvy

Staff Emeritus
"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!> 24?

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)(2k), where I have used the induction hypothesis: k!> 2k. Can you show that (k+1)(2k is greater than or equal to 2k+1? Remember that k is at least 4.

5. Nov 5, 2008

### 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.

Last edited: Nov 5, 2008
6. Nov 6, 2008

### HallsofIvy

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

How large is k+1?

7. Nov 6, 2008

### 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.

Last edited: Nov 6, 2008
8. Nov 6, 2008

### vvvidenov

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

9. Nov 7, 2008

### HallsofIvy

Staff Emeritus
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*2k is equal to 6k?

10. Nov 7, 2008

### 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 with out 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.