For Monday, February 6th

For Monday:

Proof for Feedback

Combinatorial Proof


  1. Notice that in our last class, we used the so-called “Addition Principle”, which is that if we break a count into exclusive (non-overlapping) cases, then we sum the results to obtain the full count.  For example, if we want to count subsets of size 3 or 4, then we can count subsets of size 3 and subsets of size 4 (two separate sub-problems), and add the results.
  2. Review the “combinatorial proof” we did at the end of last class (class notes in the “Materials Archive” tab above).   It’s an important example proof.  If you are unfamiliar with summation (sigma) notation, or just need a refresher, check out this explanation.
  3. Consider the binomial coefficients {{n}\choose{k}} and {{n}\choose{n-k}}.  Check for n=4 and k=1 that these are equal.  Using the formula for the binomial coefficient (last theorem in last class) to show that these are equal (for all 0 <= k <= n).  Use a counting argument (combinatorial proof) to show that these are equal (for all 0 <= k <= n).
  4. Do your proof for feedback.
  5. With remaining time, check out some practice problems from Hammack.  Section 3.3 #5, 7, 10; Section 3.4 #3, 9, 10, 14;  3.5, #3, 5, 8, 10, 17, and/or any others that interest you.  (A comment on Hammack:  I don’t teach counting the way he does.  I prefer not to subdivide counting into many “types” (e.g. lists, subsets) of problems because I believe that then the student ends up less adaptable to novel problems.  But you may still find it helpful to read Hammack.)