Proof by Induction, Part 2

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

Problem Set 6, Question 3

Prove that for all integers n and all real numbers x, n + x is irrational if and only if x is.

You can start this by noticing the biconditional, and so proving each direction separately.

Each direction has the quantifiers “for all integers n and all real numbers x…” (since the “if and only if” is inside those quantifiers).

Direction 1: if n + x is irrational, then x is irrational. Use a proof by contradiction. Assume n+x is irrational and x is rational, i.e., x = a/b for integers a and b ≠ 0. Then n + x = n + a/b = (nb+a)/b which is rational. But this is a contradiction, since n + x is also irrational.

Direction 2: if x is irrational, then n + x is irrational. Again, use a proof by contradiction. Assume x is irrational and n + x is rational. n + x = a/b, so x = a/b - n which is rational. Contradiction!

Proof by Induction

Based on section 4.1 of the textbook and this discussion of induction proofs.

Powers of Odd Numbers

(From the discussion.) Prove that if n is odd, then all natural-number powers of n (i.e., n¹, n², n³, etc.) are also odd. In other words, n^m is odd for all natural numbers m.

Induction on m. (To check that induction is a valid method here, be sure the numbers you’re doing induction on, i.e., the exponents m, are naturals)

Basis step: m = 1. n¹ = n which is odd.

Inductive step (where you show that if it works for k, it works for k+1): Since we’re proving a conditional, we can prove it like other conditionals, namely assume the hypothesis and show that the conclusion follows. So assume n^k is odd, and show that n^k+1 is odd. n^k+1 = n n^kwhich is a product of 2 odd numbers, which we know is odd.

Fibonacci Numbers

Prove that the n^th Fibonacci number is less than or equal to 2ⁿ, i.e., F_n ≤ 2ⁿ where F₀ = F₁ = 1 and F_n = F_n-1 + F_n-2 for n > 1.

We first of all realized that induction might be helpful here because both 2ⁿ and F_n can be calculated from earlier powers of 2 and Fibonacci numbers, respectfully, which is a pattern of behavior that induction fits well.

We then tried F₁ as a basis step, and found that F₁ = 1 ≤ 2¹ = 2.

Then we turned to the inductive step, where we started with F_k ≤ 2^k as an induction hypothesis. Then we started writing F_k+1 and comparing it to 2^k+1, with F_k+1 = F_k + F_k-1 ≤ 2^k + F_k-1, but here we got stuck with the F_k-1 term. It’s not covered by the induction hypothesis, which is only about F_k.

It turns out we need a slightly different form of induction, called “strong induction,” here. Strong induction lets you make an induction hypothesis about all values up to k, not just about k. In particular, we could assume both that F_k ≤ 2^k and F_k-1 ≤ 2^k-1, and then the comparison we tried to do before works: F_k + F_k-1 ≤ 2^k + 2^k-1 < 2^k+1.

As one final note on the strong induction, we noticed after finishing the inductive step that it relies on knowing that the proposition holds for all F_i where i ≤ 1, i.e., we needed another basis step for F₀. Fortunately, we were able to prove that F₀ ≤ 2⁰.

Once all of this was done, our outline of the proof looked like this:

Next

Sets again, but in more depth.

Please read section 5.1 of the textbook.

Please also contribute to this discussion of set operations. (Note: this discussion asks you to come up with examples of many of the concepts introduced in the reading; thinking of examples of key concepts is a good way to make sense of any reading, so if you’re struggling with the reading, visiting the discussion might actually help you with the textbook too.)

Next Lecture