Introduction to Induction

Return to List of Lectures

Previous Lecture

Misc

Exam 1

My solutions, in LaTeX and PDF form, are available, either by clicking the preceding links or from the “Solutions” folder in our “Files” area of Canvas.

Question 4?

• Basically asks whether the set S = { x ∈ ℤ | if x is odd then x² < 0 } is empty or not
• S is the truth set (relative to a universal set of all integers) of “if x is odd then x² < 0,“ which is true of all even integers.

Math Learning Center

“Specialists” in Math 239 available...

• Monday, 11:30 – 3:30pm, 7:30 – 9:30pm
• Tuesday, 10:30 – 3:30pm, 7:30 – 9:30pm
• Wednesday, 11:30 – 2:30pm, 7:30 – 9:30pm
• Thursday, 10:30 – 3:30pm, 7:30 – 9:30pm
• Friday, 10:30 – 2:30pm

Colloquia

Yu-Min Chung

• “Computational Topology with Applications in the Natural Sciences”
• Today (Monday), 2:30 PM, Newton 203

Eleni Panagiotou

• “Quantifying Entanglement in Physical Systems”
• Thursday, March 2, 2:30 PM, Newton 203

Both speakers are faculty candidates

Extra credit for writing a paragraph or so summarizing connections you make between either or both talks and your own interests.

Questions?

Negations?

In a proof by contradiction you negate the whole proposition, including any quantifiers.

But when using the contrapositive to prove propositions of the form “for some quantifier, if P then Q” you only apply the contrapositive to the conditional. A contrapositive is an equivalent for a conditional, so “for some quantifier, if P then Q” is equivalent to “for some quantifier, if not Q then not P.”

Complex example: what’s the negation of “for all integers m such that 2 divides m but 4 does not divide m, there exist no integers x and y such that x²+3y² = m”?

Clearing up the quantifiers and conditionals yields “for all integers m, if 2 divides m and 4 does not divide m, then for all integers x and y, x²+3y² ≠ m”

Begin by negating the outer quantifier: “there exists an integer m such that not( if 2 divides m and 4 does not divide m, then for all integers x and y, x²+3y² ≠ m)”

Next negate the conditional: “there exists an integer m such that 2 divides m and 4 does not divide m and not( for all integers x and y, x²+3y² ≠ m)”

Finally negate the inner quantifier: “there exists an integer m such that 2 divides m and 4 does not divide m and there exist integers x and y such that x²+3y² = m”

You could then carry out a proof by contradiction, i.e., assume m is an integer, 2 divides m, 4 does not divide m, and x²+3y² = m for integers x and y....

Induction

Section 4.1

Inductive sets.

Which of the following are inductive, and why?

Relevant reading ideas:

• What is an inductive set?
• Definition: Subset T of the integers is inductive provided that for each integer k, if k is in T then k+1 is in T.
• Intuitively this means that an inductive set is one that starts at some integer and then contains all larger integers.

The even natural numbers? Not inductive, since k+1 isn’t in the set when k is.

{ n ∈ ℤ | n ≥ 0 }? Yes, for every integer k ≥ 0, k+1 is also in this set.

But the reals and rationals aren’t inductive even though k being in implies k+1 is, because they aren’t subsets of the integers.

{ 2ⁿ | n ∈ ℕ }? Not inductive. { 2ⁿ | n ∈ ℕ } = { 2, 4, 8, 16, ... } so fails the k+1 requirement.

A Proof by Induction

Prove that for all natural numbers n, 2ⁿ is even.

Relevant reading ideas:

• The principle of mathematical induction: if T is a subset of ℕ and 1 is in T and for every natural number k, if k is in T then k+1 is in T, then T = ℕ.
• This is helpful if T is defined as the naturals that make some predicate true. Then showing that T satisfies the hypothesis of the principle of mathematical induction proves that the predicate holds for all naturals.
• To prove by induction that P(n) holds for all members of some inductive set
  
  • Prove P is true of the smallest integer in the set
  • Prove the conditional “if P(k) is true then P(k+1) is also true”
• So a proof by induction is really two smaller proofs

Next

Induction examples

Try to prove the proposition above, i.e., for all natural numbers n, 2ⁿ is even. Be prepared to talk about your ideas or questions at the start of class Wednesday.

Next Lecture