• Support PF! Buy your school textbooks, materials and every day products Here!

Prove by induction (discrete math's)

  • Thread starter vvvidenov
  • Start date
  • #1
23
0

Homework Statement



Prove by induction that
n!> 2^n for n[tex]\geq[/tex]4


Homework Equations



solved example:
P(n): 2^n>1+3n let n[tex]\geq[/tex]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[tex]\geq[/tex]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[tex]\geq[/tex]4
>1+3k+3k
[tex]\geq[/tex]1+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.
 

Answers and Replies

  • #2
1,631
4
assume that the proposition holds for n=k, that is

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

[tex] (k+1)!=(k+1)k!=>(IH) (k+1)k!>(k+1)2^k>2*2^k=2^{k+1}[/tex]

since [tex] k+1>2[/tex] for k>=4.
 
  • #3
23
0
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:
  • #4
HallsofIvy
Science Advisor
Homework Helper
41,833
956
"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
23
0
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. :redface:

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:
  • #6
HallsofIvy
Science Advisor
Homework Helper
41,833
956
Could you show that 3(2k)> 2k+1?

How large is k+1?
 
  • #7
23
0
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:
  • #8
23
0
How large is k+1?
n=k=4
k+1=5
Then what?
 
  • #9
HallsofIvy
Science Advisor
Homework Helper
41,833
956
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*2k is equal to 6k?
 
  • #10
23
0
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.
Thank you anyway. Please forget about this problem and delete it.
 

Related Threads on Prove by induction (discrete math's)

  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
818
Replies
7
Views
4K
Replies
5
Views
1K
  • Last Post
Replies
2
Views
888
Replies
1
Views
889
  • Last Post
Replies
4
Views
869
  • Last Post
Replies
5
Views
12K
Replies
4
Views
6K
Replies
4
Views
9K
Top