Problem Set 6—Proof by Induction

Purpose

This problem set reinforces your understanding of proof by induction, in all its forms.

Background

Our textbook covers proof by induction in sections 4.1 and 4.2. We discussed (or will discuss) it in class between March 7 and 21.

Activity

Solve the following problems. All proofs should be word-processed (i.e., not hand-written) and should follow the guidelines for formal proofs from Sundstrom’s text and class discussion.

Problem 1

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).

Problem 2

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).

Problem 3

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.

Problem 4

Exercise 18c in section 4.1 of Sundstrom’s text (critique a proof that all dogs are the same breed). This is one of a series of exercises that Sundstrom calls “evaluation of proofs” exercises; see exercise 19 in section 3.1 for a complete explanation of what you need to do for such exercises.

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.

I will use the following guidelines to grade this problem set:

• What I expect (8 points). Between your written answers and verbal explanations, I expect you to show that you understand (1) how to use weak induction (aka the first principle of mathematical induction) in proofs, (2) how to use strong induction (aka the second principle of mathematical induction) in proofs, and (3) how to formally write proofs that use induction.
• Three quarters of what I expect (6 points). A plausible, but not the only, example of a solution that would meet three quarters of my expectations for this problem set is one in which you understand both proof styles, but fail in multiple places to use proper formal conventions.
• Half of what I expect (4 points). Some plausible, but not the only, examples of solutions that would meet half my expectations include ones that show you do not understand one proof style but do understand the other, regardless of how formally the proofs are expressed, OR solutions that show you partially understand both styles (regardless of level of formality).
• Exceeding expectations (typically 1 point added to what you otherwise earn). Demonstrating that you have significantly engaged with math beyond what is needed to solve the given problems exceeds what I expect.