Math 310 Collected Homework #2: due Friday 1/21/2005

1. From the Problem Set I (textbook, pages 53-57) do problems #11, #12, #13, and #16.

2. From the Problem Set I (textbook, pages 53-57) do problem #10

3. What is wrong with the following “proof” by induction?

Theorem: All cows have the same color.

Proof.

We’ll show that for all positive integers n, in any collection of n cows all the cows have the same color. Since there are finitely many cows on Earth, this proves the stated theorem. We’ll use induction on n.

Base case n=1: Clearly in any collection of a single cow all cows have the same color.

Inductive step: Suppose now that the result is true for some n>0, so that in any collection of n cows all the cows have the same color. We need to show the result is true for n+1. Let {C₁ , C₂ , …, C_n+1} be any collection of n+1 cows. The subset {C₁ , C₂ , …, C_n} has n cows, so by hypothesis all the cows in this subset have the same color. On the other hand, all the cows in the subset {C₂ , …, C_n+1} must also have the same color, again by induction hypothesis. It thus follows that C_n and C_n+1 must have the same color. Combining this with the previous observation that all the cows in {C₁ , C₂ , …, C_n} have the same color, if follows that all of {C₁ , C₂ , …, C_n, C_n+1} must have the same color. We have proved the inductive step, so the proof is complete.

Hence all the cows have the same color. QED.

4. Let m and n be any integers. Show that the product mn is odd if and only if both m and n are odd.

Note : “if and only if” means “<=>”, so you need to show that both implications “ =>” and “<=” hold.