MATH 2602 Homework #4-#7
Due Wednesday Feb 4 - Feb 25, covering the material of Exam 1 on Feb 25

• Homework 4 - Due Feb 4
• Core : Book problems: Section 6.1 on page 191 problems 1, 2, 3, 10.
  Section 6.2 on page 198 problems 10, 23.
  Section 6.3 on page 203 problems 2, 3, 8, 9.
  Also, 
  • A1: Prove the following for any sets A,B.
    If A and B have no elements in common, then the number of elements in the union
    of A and B is equal to the number of elements in A plus the number of elements in B.
  • A2: Prove the converse of the statement in A1.
  • A3: Prove the following for any finite sets A,B. If A has n elements
    and B has m elements, then AxB has nm elements.
  • A4: Let R be an equivalence relation on a set A with 10 elements.
    Prove that either there are more than 3 equivalence classes of A or
    at least one equivalence class has at least three elements in it.
• Homework 5 - Due Feb 11
• Core : Book problems: Section 7.1 on page 209 problems 1, 2, 7a-d, 10, 11, 15.
  Section 7.2 on page 215 problems 1, 2ab, 3, 5a, 8, 10, 12, 18.
• Homework 6 - Due Feb 18
• Core : Book problems: Section 5.1 on page 157 problems 1ab, 3, 4dgk, 5a, 6e.
  Section 5.2 on page 167 problems 1, 3, 6.
  Section 5.3 on page 174 problems 2, 6, 8, 13a.
  
• Also: Find a formula for ½+¼+⅛+…+1⁄2ⁿ by examining the values of this expression for small values of n. Prove that your formula is correct for all values of n.
  
• Also: the following problem doesn't quite fit in this section, but I really like it. Thanks to George Kerchev for showing it to me:
  There are 77 dominoes on a table. A two-player game consists of each player removing anywhere from 1 to 11 dominoes on their turn.
  A player wins if they take the last turn, removing all the dominoes left on the table.
  Show that the player who goes first has a strategy where they are guaranteed to win.
  If instead there are 72 dominoes, show that the second player has a guaranteed-to-win strategy.
• Homework 7 - Due Feb 25
• Core : Book problems: Section 8.1 on page 252 problems 11, 13.
  Section 8.2 on page 264 problems 5, 7bdf, 8bdf, 10a.
  Section 8.3 on page 275 problems 1ab, 2a, 6ab, 7, 11, 13.
• Also: (a) For n≥0, give a recurrence relation for the number an of ways to fill a 2×n chessboard using non-overlapping *dimers*, or tiles of dimension 2×1.
  For example, a₄ = 5 since there are five such tilings (see picture)
  
  You may assume a₀ = 1.
  (b) The sequence a₀,a₁,a₂,... is a well-known sequence. What is it?