MATH 131A Week 1 Group Worksheet
January 9, 2024
Instructions: You are encouraged to work on these problems with your assigned group. At the end of discussion, each group should submit a single sheet with clean, well-justified proofs for each problem.
Problem 1. Consider the statement
P = the square of an odd number is odd.
(a) What is the converse of P?
(b) What is the contrapositive of P?
(c) Prove P directly.
(d) Prove P by contradiction.
Problem 2. Prove that 1 + 2 + 4 + ... + 2n- 1 = 2n — 1 for all ne N.
Problem 3. (Strong Induction) An alternative to using regular induction is a proof technique called strong induction. In strong induction, the base case P(1) remains the same. For the inductive step, instead of only supposing that P(n) is true, one assumes that all of P(1),..., P(n) are true and uses that to conclude that P(n + 1) is true.
Use strong induction to prove the following statement: Every positive integer n > 8 can be written as a sum of 3’s and 5’s.
Problem 4. Prove the Fundamental Theorem of Arithmetic: Every positive integer n > 2 can be factored as a product of primes. Moreover, any two such factorizations are equivalent up to rearrangement of prime factors. You may assume Euclid’s lemma: if a prime p divides the product of two integers ab, then either p divides a or p divides b. (Hint: Use strong induction).
Bonus Problem. Here is an erroneous proof by mathematical induction that all horses are the same color. Define the statement P(n) = ”any n horses are the same color” for n e N. For simplicity, we assume that a horse cannot be two different colors at once.
Proof. Base Case: Let n = 1. Then, in a set with one horse, every horse is obviously the same color.
Inductive Step: Suppose that every n horses have the same color. Consider any n + 1 horses. Take the first n horses. By the inductive assumption, they are all the same color, say, black. Now, take the last n horses. They are also all the same color. But we know that all horses in the middle are black, so the last n horses are black. Thus, all n+ 1 horses are black. 
Write a brief summary of where and why this induction argument fails.