Review of Induction

Return to Course Outline

Previous Lecture

Misc

Exam 2

Exam 2 is Wednesday (April 3).

Covers proof techniques and possibly quantifiers (e.g., for all, there exists, contrapositive, biconditionals, contradiction, cases, induction — problem sets 4 through 6).

Rules and format will be similar to exam 1, particularly open-references rule. But there may be slightly fewer questions, because more of the questions will ask you to write proofs.

Sample questions are available in Canvas.

Mid-Semester Feedback

Putting formal versions of class proofs in Canvas is good.

Group work in class is good.

Grading appointments are good.

Projected Canvas notes in class are good, be sure they’re readable.

End class on time.

Rely more on volunteers than random names to start conversations.

Vote (thumbs up/thumbs down) on whether to switch from group work to discussion.

More time on induction.

Questions?

Another strong induction example?

Conjecture: every natural number greater than or equal to 6 can be written as 3a + 4b for non-negative integers a and b.

The first step was to come up with 6 as the bound at which this conjecture starts to hold. That was mostly a trial and error process of trying successively bigger numbers until 3 or 4 in a row could be written as 3a + 4b.

The next step was to formally prove the conjecture, via strong induction. The formal proof is here, and its LaTeX code is here.

Comments:

• When developing an induction proof, it’s probably a good idea to start with the induction step, because knowing whether it needs an assumption about k, or numbers less than k, tells you whether you’ll need weak induction or strong, and, if strong, how many basis cases you’ll need.
• Although many of our recent examples have been strong induction, weak induction is probably slightly more common.
• While this induction review was triggered by the mid-semester feedback, if there are future topics that you’d like to spend more time on let me know, because we can probably do it.

Next

(After exam)

Cartesian products, section 5.4.

Next Lecture