Problem Set 7 — Proof by Cases and Induction

Purpose

This problem set gives you practice writing proofs using cases, and proofs using induction. It thus addresses the following learning outcomes:

• Outcome 5.4, Recognize claims amenable to proof in cases 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 cases 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 in cases are discussed in section 3.4 of our textbook. We talked about them in the March 19 class.

Proof by induction is the subject of chapter 4 of the textbook, and particularly section 4.1. We talked about it, or will talk 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, 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 5a in section 3.4 of Sundstrom’s text (prove that for all integers \(a\), \(b\), and \(d\) with \(d \ne 0\), if \(d\) divides \(a\) or \(d\) divides \(b\), then \(d\) divides \(ab\)).

Problem 2

Exercise 7 in section 3.4 of Sundstrom’s text (determine whether it is true or false that for all integers \(n\), if \(n\) is odd then \(8 | (n^2 - 1)\); prove the proposition or provide a counterexample, according to whether you think it is true or false). Recall that the notation \(a | b\) means “\(a\) divides \(b\),” i.e., \(b = ka\) for some integer \(k\).

Problem 3

Prove that for all natural numbers \(n \ge 2\), the product

In slightly less rigorous, but perhaps easier to understand, form, the claim is

Problem 4

Based on exercise 15d in section 4.1 of Sundstrom’s text: prove that for all natural numbers \(n\), the \(n^{\mathrm{th}}\) derivative of

is

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.