Problem Set 9—Proof by Induction, Sets

Purpose

This problem set reinforces your understanding of strong and extended induction. It also begins to develop your ability to reason about set operations.

Background

This problem set is based on material in sections 4.2 and 5.1 of our textbook. We discussed section 4.2 in class on March 3 and 6. We discussed section 5.1 on March 20.

Activity

Do the following exercises. All proofs should be word-processed (i.e., not hand-written) and should follow the guidelines in Sundstrom’s text.

Exercise 1

Exercise 4d in section 4.2 of Sundstrom’s text (state and prove a proposition about the product (1 - 1/4)(1 - 1/9)…(1 - 1/n²); see the textbook for more information; you may find it helpful to look at exercises 4a and 4b, although you aren’t required to).

Exercise 2

A variation on exercise 7 in section 4.2 of Sundstrom’s text: formulate a proposition of the form “for all natural numbers n greater than or equal to ___, there exist nonegative integers x and y such that n = 4x + 5y,” where “___” represents a constant to be discovered by you. Then prove your proposition.

Exercise 3

Exercises 8a, 8b, and 8c in section 5.1 of our textbook (given that the universal set is ℕ, find A ∩ B, A ∪ B), and (A ∪ B)^C where A is the set of natural numbers greater than or equal to 7 and B is the set of odd natural numbers).

Exercise 4 (Proofs Out of Context)

This problem continues the set of out of context problems from Prof. Nicodemi that we started in Problem Set 5. From that problem set, recall the following, all of which you can now take as proven:

Fact 1. For all real numbers x and y, if x > 0 then there is a natural number n such that nx > y.

Proposition 1. For all real numbers x, if x > 0 then there is a natural number n such that 0 < 1/n < x.

Now prove the following. You will probably find one or more of the statements above to be helpful:

Proposition 2. For any real numbers x and y such that x < y, there is a natural number n such that ny - nx > 1.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.