Test 2 Version 2

  1. Consider the word
  2. Prove the following instance of van der Monde's theorem by giving a combinatorial proof:

          C(13,4) = SUM(  C(8,4-k) * C(5,k) : k=0..4 ) 

    Well you have seen the proofs. Your proof must adequately mention sets, partitions, and correspondences between sets.

  3. Here we have an inductively defined set S of bit strings:

    Decide if it is true that S is simply the set of all strings which do not have two consecutive 1's and then prove, likely using induction, your answer. That is, first prove whether or not every member of S has this property. Then prove whether or not every string with this property is in S.

    As said on the test (to get familiar with the construction) 0 is in S. Indeed, apply the generation (second) rule by taking u and w be lambda. Thus we have that u and w are in S, hence 0 = lambda 0 lambda is in S.

    Let P(n) be the statement that every string in S of length n has no consecutive 1's.

    Let Q(n) be the statement that every string of length n which does not have consecutive 1's in in S.

    We first prove P(n) by induction. Both 0 and 1 are in S and clearly neither has consecutive 1's, hence P(1) is true. Obviously P(0) is also true.

    Now suppose that P(k) is true for all k< n+1 for some positive integer n. Fix any string s in S which has length n+1. The only way for s to get into S is by the generation rule. Therefore there are strings u,w in S such that s= u 0 w. Clearly u and w are strings in S with length less then n+1 hence they do not have consecutive 1's. It is now apparent that u 0 w = s also does not have consecutive 1's.

    Now we prove Q(n) by induction. We have already checked above that Q(0) and Q(1) are true (i.e. lambda, 0 and 1 are all in S). Now suppose that n is a positive integer and that Q(k) is true for all k< n+1 (i.e. the strong principle of induction).

    We must take a string s which has no consecutive 1's and has length n+1 and prove that s is in S. Ok, obviously s must have a 0 in it somewhere (it has length at least 2 and no consecutive 1's). Pick one of the positions in s where it is a 0, and let u be all the bits in s before that position and let w be all the bits in s after that position. Clearly s is equal to u 0 w. What about this u and w. Each has length strictly less than s and neither will contain consecutive 1's. Therefore by the inductive assumption, each is in S. Now using the generation rule for S, we see that u 0 w must also be in S.