View Single Post
  #2  
Old 08-24-2018, 10:16 PM
chrchrchr23 chrchrchr23 is offline
Junior Member
 
Join Date: Aug 2018
Posts: 1
Default Re: *ANSWER* HW 3, Questions 6, 7, 8

question 7 just used what was proved in lecture 6

C(n,k)=C(n-1,k)+C(n-1,k-1)

since break point k=5

B(n,k)<=C(n,4)+C(n,3)+C(n,2)+C(n,1)+C(n,0)

=(C(n,4)+C(n,3))+(C(n,2)+C(n,1))+C(n,0)

=C(n+1,4)+C(n+1,2)+1




question 8:

with M intervals you can only have M disjoint "+1" intervals

with a dichotomy that has M+1 disjoint "+1" intervals you've reached the breakpoint

each interval contains a minimum of 1 such "+1" point, that's M+1 points

seperate them with a minimum of M "-1" points

you get break point k=(M+1)+M=2M+1
Reply With Quote