cs2102
Discrete Mathematics

Class 11: Induction Practice


Schedule

Problem Set 5 is due Friday at 6:29pm.

Thursday’s Class may include review for Exam 1. Before 6:59pm Wednesday, send uvacs2102staff@gmail.com topics you would like to review:

  • fewer than 10 total requests: class is not being sufficiently challenged and we should be doing more difficult material (except for the 10 requestors who get exam exemptions).
  • exactly 10 total requests: all requestors get automatic exam exemptions, review requested topics.
  • more than 10 requests implies we should spend Thursday’s class on reviewing requested topics, no exam exemptions.

Exam 1

Exam 1 will be in class on Thursday, 5 October. You can get a good idea what to expect on Exam 1 by looking at the Practice Exam 1 (from last year’s class). We strongly encourage you to try to problems on your own, before looking at the posted solutions.

Resources. You will be permitted to use a single paper page of notes that you prepare and bring to the exam. It is fine to collaborate with others to prepare your notes. The page should be no larger than a US Letter size page ($8.5 \times 11$ inches), and you may write (or print) on both sides of the page. You may not use any special devices (e.g., magnifying glasses) to read your page. No other resources, other than your own brain, body, and writing instrument, are permitted during the exam.

Content. The problems on the exam will cover material from Classes 1–11, Problem Sets 1–5 (including the provided solutions), and MCS Chapters 1–5. Everything on the exam will be something you have seen in at least two of these (Classes, Problem Sets, and MCS Book), and most of the exam will be things you have seen in all three. If you understand the problems on the problem sets and questions on the class notes well enough to be able to answer similar questions, you should do well on the exam.

The main topics the exam will cover include:

  • Propositions, axioms, and proofs (you should understand what each of these are and how to define them precisely)

  • Inference rules (how to determine and show if an inference rule is sound or unsound, how to correctly use inference rules in a proof)

  • Logical formula (how to interpret logical formulas and convert English statements into logic, determine the validity or satisfiability of a formula, and show equivalence or non-equivalence of two formulas)

  • Logical quantifiers (how to reason about logical formula using $\forall$ and $\exists$, including showing logical equivalence and implication)

  • Proof methods (you should be able to read and write proofs that use direct proof, contrapositive proof, and proof by contradiction)

  • Well ordering (you should be able to explain what it means for a set to be well ordered, determine if a given set and operator is well ordered, and be able to construct proofs using the well ordering principle and identify flaws in misuses of the well ordering principle)

  • Induction (you should understand mathematical induction and be able to construct proofs using induction and identify flaws in misuses of induction in proofs)

For most students, we believe the best way to prepare for the exam will be to (1) go over the problem sets and their solutions, and make sure you understand well any of the problems you did not get before; (2) go through the provided practice exam and try to solve all the problems on your own before reading the solutions; (3) go through the questions in the class notes and convince yourself you can answer them well; (4) re-read chapters of the book, solving the associated practice problems, especially for any sections on topics where you had difficulty on the problem sets. If you do #1 and #2 and understand well the problems on the practice exam, you should be confident you’ll do well on the exam; if you struggled on the problem sets, you would benefit from doing #3 and #4 as well.

See PDF Version for Notes and Questions.

Induction Principle

Let $P$ be a predicated on $\mathbb{N}$. If

  • $P(0)$ is true, and
  • $P(n) \implies P(n + 1)$ for all $n \in \mathbb{N}$,

then

  • $P(m)$ is true for all $m \in \mathbb{N}$.

Prove: For all sets $A$, $|pow(A)| = 2^|A|$.

Prove: The sum of the first $n$ positive integers is $\frac{n(n+1)}{2}$.

Generalizing to Well-Ordered Sets

We can use Induction for any well-ordered set, where there is an operation (like ‘+ 1’) and a starting point (like ‘0’) that covers the whole set.

Prove. All non-empty finite subsets of $\mathbb{N}$ have a minimum element.

Induction Practice

Take-Away Game: start with $n$ sticks; at each turn a player must remove 1, 2 or 3 sticks; player who takes the last stick wins.

  • Prove: for a Take-Away game with any initial number of sticks, $n$, either Player 1 has a winning strategy or Player 2 does.

  • Prove: Player 1 has a winning strategy for a Take-Away game with $n$ sticks, if \bigfillin. Otherwise, Player 2 has a winning strategy.