Introduction to Mathematical Analysis I - Second Edition

15 1.2.6 Prove parts (1), (3), and (4) of Theorem 1.2.4 . 1.2.7 Prove parts (2), (3), and (4) of Theorem 1.2.5 . 1.2.8 Prove parts (1), (2), (3), and (5) of Theorem 1.2.6 . 1.2.9 Prove that the union of two finite sets is finite. Hint: it is easier to show when the sets are disjoint. 1.3 THE NATURAL NUMBERS AND MATHEMATICAL INDUCTION We will assume familiarity with the set N of natural numbers, with the usual arithmetic operations of addition and multiplication on N , and with the notion of what it means for one natural number to be less than another. In addition, we will also assume the following property of the natural numbers. Well-Ordering Property of the Natural Numbers: If A is a nonempty subset of N , then there exists an element ` ∈ A such that ` ≤ x for all x ∈ A . To paraphrase the previous property, every nonempty subset of positive integers has a smallest element. The principle of mathematical induction is a useful tool for proving facts about sequences. Theorem 1.3.1 — Principle of Mathematical Induction. For each natural number n ∈ N , suppose that P ( n ) denotes a proposition which is either true or false. Let A = { n ∈ N : P ( n ) is true } . Suppose the following conditions hold: (a) 1 ∈ A . (b) For each k ∈ N , if k ∈ A , then k + 1 ∈ A . Then A = N . Proof: Suppose conditions (a) and (b) hold. Assume, by way of contradiction, that A 6 = N . Set B = N \ A , that is, B = { n ∈ N : P ( n ) is false } . Then B is a nonempty subset of N . By the Well- Ordering Property of the natural numbers, there exists a smallest element ` ∈ B . By condition (a), 1 6∈ B . Hence, ` ≥ 2. It follows that k = ` − 1 is a natural number. Since k < ` , k 6∈ B and, hence, we have that P ( k ) is true. By condition (b), we obtain that P ( k + 1 ) is true. But k + 1 = ` , and P ( ` ) is false, since ` ∈ B . This is a contradiction, so the conclusion follows. To paraphrase, the principle says that, given a list of propositions P ( n ) , one for each n ∈ N , if P ( 1 ) is true and, moreover, P ( k + 1 ) is true whenever P ( k ) is true, then all propositions are true. We will refer to this principle as mathematical induction or simply induction. Condition (a) above is called the base case and condition (b) the inductive step . When proving (b), the statement P ( k ) is called the inductive hypothesis . Example 1.3.1 Prove using induction that for all n ∈ N 1 + 2 + · · · + n = n ( n + 1 ) 2 . The statement P ( n ) is the equality 1 + 2 + · · · + n = n ( n + 1 ) 2 . Now the base case says that 1 = 1 ( 1 + 1 ) 2 , which is clearly true.