Math 299: Introduction to Mathematical Proof

Daily Activities and Problem Sets:

Assignment #25 – Thursday, May 11, 2016

  • 0. Keep working on the Term Paper portion of the Final Exam.To help keep you on track, put a draft of your Take Home Final Exam pdf in Dropbox before Tuesday. It should contain at least five of the six proofs. I won’t grade them for correctness until your final draft but I will give you a homework grade for making progress.
  • 1.  Write up and hand in a combinatorial proof for each of the following. Write your proofs in LaTeX using the math299.sty and put your pdf file in Dropbox as usual.  You cannot use any algebra, subsitution, or previous formulas derived in class. Just 100% pure counting!
    • Theorem A: $\binom{6}{2}\cdot\binom{4}{3}=\binom{6}{3}\cdot\binom{3}{2}$
    • Theorem B: For all combinatorial expressions $n$ and $k$ with $2\leq k\leq n$ $$\binom{2n+2}{k}=\binom{2n}{k}+2\binom{2n}{k-1}+\binom{2n}{k-2}$$
    • Theorem C: For all combinatorial expressions $n$ $$\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n}=2^n$$ [Note: this says that if we add up a row of Pascal’s triangle we always get a power of two.  Try it and see for yourself! Of course you can’t use that as a proof, I’m just pointing out that the theorem is cool.]