Strong Induction, Part 2

Return to List of Lectures

Previous Lecture

Misc

Exam 2

Wednesday, March 8

Covers material since the first exam, mainly proof techniques (e.g., contrapositive, biconditionals, contradiction, cases, induction) but maybe also contexts such as congruence. See chapters 3 and 4, and problem sets 5 - 8.

Expect 3 - 4 questions, probably focusing more on proofs than in exam 1. Otherwise similar in style and rules to exam 1, especially open-references but closed person.

I’m Out of Town Later this Week

I leave right after the exam Wednesday.

But Nicole would like your help for the Friday class...

Questions?

Strong Induction

Example. Finish proving that for all n, F_n < 2ⁿ.

Last time we showed two basis cases, namely that F₁ = 1 < 2 = 2¹ and F₂ = 1 < 4 = 2².

We started an inductive step by assuming that F_i < 2ⁱ for all 1 ≤ i ≤ k, and by trying to show that F_k+1 < 2^k+1. We got as far as realizing that F_k+1 = F_k + F_k-1 < 2^k + 2^k-1. Now what? F_k+1 = F_k + F_k-1 < 2^k + 2^k-1 = 2^k-1(2 + 1) = 3 2^k-1 < 4 2^k-1 = 2^k+1. QED

The Extended Principle of Mathematical Induction

Example (a rigorous proof of an extended version of Sundstrom’s Theorem 3.28). Prove that if a ≡ b (mod n), then for all non-negative integers m, a^m ≡ b^m (mod n).

Relevant reading ideas or questions?

• The extended principle: you can start induction at any integer M

Proof by induction on m.

Basis step: m = 0. Show that if a ≡ b (mod n), then a⁰ ≡ b⁰ (mod n). The congruence holds because a⁰ = b⁰ = 1, and 1 ≡ 1 (mod n).

Induction step: Assume a^k ≡ b^k (mod n) and show a^k+1 ≡ b^k+1 (mod n). {scratch work: hmm, a^k+1 = a a^k, similarly for b; maybe this can provide a connection between the induction hypothesis and what we want to show.} We know from this theorem’s hypothesis that a ≡ b (mod n), and from the induction hypothesis that a^k ≡ b^k (mod n), so from part B of Theorem 3.28 {reminder: part B says that if x ≡ y (mod n) and w ≡ z (mod n) then xw ≡ yz (mod n)} we have that a a^k ≡ b b^k (mod n), or in other words that a^k+1 ≡ b^k+1 (mod n).

Example (extended and strong induction). Prove that for sufficiently large n, F_n > (√2)ⁿ. We didn’t do this in class, but it could be an interesting exercise for the reader. Combined with the strong induction example from earlier it shows that the Fibonacci numbers lie between two simple exponential functions. This new example also requires a combination of extended induction and strong induction, with the extended induction having a less trivial basis case than the previous example did.

Next

(After break)

Operations on sets

Read section 5.1

Next Lecture