Introduction to Proofs: Inquiry-Based Workbook

Overview of the complete resource

Source page 1–14

This is Jim Hefferon’s original compact inquiry-based workbook, not a shortened book generated by LawSphereX. Its definitions and sequences of exercises guide students through divisibility, induction, division, primes, sets, functions, inverses, relations, equivalence classes and partitions. Students develop and discuss proofs rather than read a long sequence of supplied solutions. The author describes the compact version as seven sheets of paper. Use it with a teacher, study group or a careful written proof journal. The MIT induction lecture is supplementary instruction from another course; it does not provide solutions to this workbook. This summary covers the entire resource.

Original workbook: induction preview

Source page 4

Section 1 — 11 EXERCISE

INTERLUDE: INDUCTION The results in the prior section need only proof techniques that many people find come naturally. However some results to follow require a technique that is less natural, mathematical induction. This section introduces it. (We will start with exercises about summations. However, note that induction is not about only summation. They just make good starting exercises.) For example, many people have, in playing with numbers, noticed that the odd natural num- bers sum to perfect squares: 1+3 = 4, 1+3+5 = 9, 1+3+5+7 = 16, etc. We will prove the statement, “The sum 1+3+5+···+(2n +1) equals (n +1)2.” That statement has a natural number variable n that is free, meaning that setting n to be 0, and 1, etc., gives a family of statements: S(0), and S(1), etc. For instance, the statement S(1) asserts that 1+3 equals 22. Our induction proofs will all involve statements with one free natural number variable. These proofs have two steps. For the base step we will show that the statement holds for some initial number i ∈N (sometimes there is a finite list of initial numbers). The inductive step is more subtle; we show that the following implication holds. If the statement holds from the initial number or numbers through the n = k case, then the statement holds also in the next case, where n k (∗) = +1. The Principle of Mathematical Induction is that proving both the base and inductive steps shows that the statement is true for all natural numbers greater than or equal to the initial number. For the intuition behind that principle, consider again the statement about odds and squares. The base step directly verifies the statement for the initial number, 0. Then, because the implica- tion (∗) holds in all cases, applied to the k = 0 case it gives that the statement holds also for the number 1. That is, (∗) with k = 0 says that S(0) implies S(1), and because we have verified S(0), we conclude that S(1) holds. Continuing on, (∗) with k = 1 says that S(0) and S(1) together imply S(2), so we know that S(2) holds. In this way, induction bootstraps to all natural numbers. Here is the full proof that 1+3+5+···+(2n +1) = (n +1)2 for all n ∈N. Proof. We will show this by induction. For the n = 0 base step, the sum on the left has a single term,1, which equals the value on the right, 12. For the inductive step, assume that the formula is true for the n = 0, n = 1, ..., n = k cases, and consider the n = k+1 case. The sum is 1+3+···+(2k+1)+ ¡2(k+1)+1 ¢ = 1+3+···+(2k+1)+(2k+3). The inductive hypothesis is that the statement is true in the n = k case. So we can substitute, 1 + 3 + ··· + (2k + 1) + (2k + 3) = (k + 1)2 + (2k + 3) = (k2 + 2k + 1) + (2k + 3) = (k + 2)2. This is the required value for the n = k +1 case. 1.11 EXERCISE. Prove by induction. A. 0+1+2+3+···+n = n(n +1)/2 B. 0+1+4+9+···+n2 = n(n +1)(2n +1)/6 C. 1+2+4+8+···+2n = 2n+1 −1 1.12 EXERCISE. Prove each by induction. Assume that a,b,r ∈R and that r̸ = 1. 2 n A. (GEOMETRIC SERIES) 1+r +r +···+r = (r n+1 −1)/(r −1) B. (ARITHMETIC SERIES) b +(a +b)+(2a +b)+···+(na +b) = (n(n +1)/2)· a +(n +1)·b 1.13 EXERCISE. Prove by induction that n < 2n for all n ∈N. 1.14 EXERCISE. Prove each by induction. A. For all n ∈N, the number n2 +n is even. B. For all n ≥2 the number n3 −n is divisible by 6. Hint: use n = 2 for the base step. C. If n ∈Z+ then (1+ 1/1)·(1+ 1/2) ··· (1+ 1/n) = n +1. 1.15 EXERCISE. Prove that sums of reals commute: a0 + a1 + ··· + an = an + ··· + a0 for all n ≥1, starting from the assumption that sum of two terms commutes. Many induction arguments use only the n = k part of the hypothesis but some use other parts. – Page 2 –