Re: *ANSWER* HW 3, Questions 6, 7, 8
question 7 just used what was proved in lecture 6
C(n,k)=C(n1,k)+C(n1,k1)
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
