Problem Set 8 — Proof Technique Review

Purpose

This problem set is a chance to review proof by induction and proof by contradiction, two techniques that many students find to be some of the harder of the common proof methods. It thus addresses the following learning outcomes:

• Outcome 1.1, Prove equivalence of statements involving Boolean connectives
• Outcome 5.3, Recognize claims amenable to proof by contradiction and construct the corresponding proofs*
• Outcome 5.5, Recognize claims amenable to proof by induction and construct the corresponding proofs*
• Outcome 7, Write solutions to problems and proofs of theorems that meet rigorous standards based on content, organization and coherence, argument and support, and style and mechanics.

(* While the proofs that this problem set asks for can be done using contradiction and/or induction, I will accept valid proofs that use other methods if you find them, and will credit grades for those proofs to the appropriate learning outcomes.)

Background

Proofs by contradiction are discussed in section 3.3 of our textbook. We talked about them in class on March 15 and 17.

Proof by induction is the subject of chapter 4 of the textbook, and particularly section 4.1. We talked about it in class meetings between March 26 and 31.

Activity

Solve the following problems.

Beware that a proof that asserts that some pattern continues throughout a sequence of values of indeterminate length, often indicated by a phrase such as “and so forth” or a synonym, or use of ellipsis (“…”) in a formula, is not rigorous. Induction can almost always get rid of the “and so forth” and make the proof rigorous.

Write any proofs as formal proofs, following the usual mathematical conventions, including typeface rules (e.g., italic variable names, emphasized labels for theorems and proofs, etc.)

Problem 1

Exercise 9 in section 3.3 of Sundstrom’s text (decide whether it’s true or false that $\sqrt{x+y}\le \sqrt{x}+\sqrt{y}$ for all positive real numbers $x$ and $y$; give a counterexample or proof to support your decision; note that $\sqrt{x}$ without any “$\pm$” denotes the positive square root of $x$).

Problem 2

Exercise 17 in section 3.3 of Sundstrom’s text (determine whether it is true or false that for all integers $n>1$, the smallest factor of $n$ that is bigger than 1 is prime; prove the proposition or provide a counterexample, according to whether you think it is true or false; see the book for more discussion of this problem).

Problem 3

Does De Morgan’s law for the negation of a conjunction extend to conjunctions involving more than 2 terms? Recall that the relevant law says that

I am asking you whether the more general rule

is true for all natural numbers $n\ge 2$.

Either prove your answer, or give a counterexample.

Problem 4

Exercise 18c in section 4.1 of Sundstrom’s text (explain what’s wrong with an induction “proof” that all dogs are the same breed; see the textbook for the alleged proof and more explanation of the problem).

Follow-Up

I will grade this exercise during one of your weekly individual meetings with me. That meeting should happen on or before the “Grade By” date above. During the meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Sign up for the meeting via Google calendar. Please have a written solution to the exercise ready to share with me during your meeting, as that will speed the process along.