Math8 HW9 - Hw9 PDF

Preview

Summary

Hw9...

Description

Math 8

Homework 09 Due Thursday, November 14th , 2019 by 8:00am

I have added some more problems to this set. Please check the next page! Complete these problems on your own paper. For each problem, clearly label the problem number (and letter, if applicable), and copy the problem statement. Then give your solution, showing all of your work in a clear, organized manner using complete sentences for any exposition. Please refer to the syllabus for information about academic honesty and cheating on HW. YOU MUST STAPLE YOUR WORK BEFORE TURNING IT IN. Turn-In Problems 1. (Hammack 6.10, adapted) Using proof by contradiction, prove that there are no integers a and b for which 20a + 15b = 1. 2. (Velleman 3.2.6 ) Use the method of proof by contradiction to prove the theorem in Velleman’s Example 3.2.5: Theorem. Suppose that A ⊆ B, a ∈ A, and a 6∈ B \ C. Then a ∈ C . 3. (Velleman 3.2.12 ) Consider the following incorrect theorem: Incorrect Theorem. Suppose that A ⊆ C, B ⊆ C, and x ∈ A. Then x ∈ B . (a) What’s wrong with the following proof of the theorem? Proof. Suppose that x 6∈ B. Since x ∈ A and A ⊆ C, x ∈ C. Since x 6∈ B and B ⊆ C, x 6∈ C . But now we have both x ∈ C and x 6∈ C , so we have reached a contradiction. Therefore x ∈ B.  (b) Show that the theorem is false by giving a counterexample. 4. An equivalence relation on a set A is a subset R ⊆ A × A that satisfies three conditions: (i) Reflexivity: (x, x) ∈ R for all x ∈ A (i) Symmetry: (x, y) ∈ R if and only if (y, x) ∈ R (i) Transitivity: If (x, y) ∈ R and (y, z) ∈ R, then (x, z) ∈ R Show that equivalence mod n is an equivalence relation, according to this definition. That is, for a fixed integer n ≥ 2, show that: (a) (Reflexivity) k ≡ k (mod n) for all k ∈ Z, (b) (Symmetry) k ≡ m (mod n) if and only if m ≡ k (mod n), and (c) (Transitivity) If k ≡ m (mod n) and m ≡ ℓ (mod n), then k ≡ ℓ (mod n). 5. (Hammack 10.8) If n ∈ N, then 1 2 3 1 n . = 1− + + + ··· + (n + 1)! (n + 1)! 2! 3! 4! Hint: Remember that n! is the product of the natural numbers up to n: n! = 1 · 2 · 3 · · · (n − 1) · n. For example, 5! = 5 · 4 · 3 · 2 · 1 = 120. 6. (Hammack 10.10 ) Prove that for all integers n ≥ 0, 3 | (52n − 1).

7. Recall that Fk , the kth Fibonacci number, is defined by F0 = 0,

F1 = 1

and

Fn+1 = Fn + Fn−1

for n ≥ 2. (a) (Hammack 10.28 ) Prove that F2 + F4 + F6 + F8 + . . . + F2n = F2n+1 − 1. 8. Use strong induction to prove that, using 2 cent and 7 cent stamps, we can exactly produce every postage amount of at least 6 cents. Do so using the smallest possible number of base cases.

Credits: Hammack refers to Richard Hammack’s Book of Proof. Velleman refers to Daniel J. Velleman’s How To Prove It, Second Edition....