Problem Set 8—Proof by Induction

Purpose

This problem set develops your understanding of inductive sets and your ability to write proofs that use induction, in both its first (weak) and second (strong) forms. This exercise also reinforces habits of formal proof writing.

Background

This problem set is based on material in sections 4.1 and 4.2 of our textbook. We discussed or will discuss this material in class on October 17, 19, 21, and possibly 24.

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, particularly the new guideline of clearly identifying proofs by induction and their basis and induction steps.

Exercise 1

Is the set { 4n-1 | n∈ℕ } inductive? Why or why not?

Exercise 2

Exercise 3c in section 4.1 of Sundstrom’s text (use induction to prove that for each natural number n, 1³ + 2³ + … + n³ = (n(n+1)/2)²).

Exercise 3

Exercise 15 in section 4.1 of Sundstrom’s text (essentially, formulate and prove a conjecture about what the n^th derivative of e^ax is in terms of a, n, and e^ax, where a is a real constant).

Exercise 4

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.

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.