Mathematical Induction Explained: Study Guide

Proofs with Quantifiers The method of induction is a general process for proving statements about all natural numbers by first proving that the statement holds for one specific number x, and then using that fact to show that it then holds for all natural numbers. This method of proof builds on smaller cases and uses them to prove larger cases, hence the name induction, which means "to build up." But first, let's look at how we might prove an existing statement. ∃𝑥𝐴(𝑥) To prove that there are irrational numbers r and s such that r to the power s is rational, one considers two cases: if , then r = s = 2; otherwise, case 1: if can be expressed as the ratio of two cubes, r = ks where k is an integer. Because (2)2 is even and so is ks, therefore. Case 2: if it is not equal to a ratio of two cubes it must have an irrational square root; hence we can find an irrational number r satisfying. 𝐼𝑓 2 2 𝑖𝑠 𝑟𝑎𝑡𝑖𝑜𝑛𝑎𝑙, 𝑡𝑎𝑘𝑒 𝑟 = 𝑠 = 2 If the square root of 2 is rational, then there are numbers r and s such that r to the power s is rational. If this assumption is not true, then we must assume that the square root of 2 is irrational. In this case, take the square root of 2 and set it equal to s. 𝐼𝑓 2 2 𝑖𝑠 𝑖𝑟𝑟𝑎𝑡𝑖𝑜𝑛𝑎𝑙, 𝑡𝑎𝑘𝑒 𝑟 = 2 2 𝑎𝑛𝑑 𝑠 = 2 And if we do that then add to the power s is root 2 to the root 2 all to the root 2. Which by the way that exponents work is root 2 to the power of root 2 times root 2 which is root 2 squared, which is 2. 𝑠 𝑟 = ( ) 2 2 2 = ( 𝑧) 2 2 2 = ( 2) = 2 We can assume that the number 2 to the power 2 is irrational, and if it is irrational, we can find an irrational number r and an irrational number s such that r to the s is 2. If root 2 to the root 2 turns out to be rational, then we take r to be this number and s to be that number; r to the s is 2. Since we don't know which of these is the case, we need not prove which is the case. Instead, we look at both cases and take different irrationals r and s for each case. By choosing r to the s to be rational in one case and irrational in the other, we are able to show that this number is either rational or irrational. Well, now let's take a look at how we might prove a statement involving a universal quantifier. Suppose we wanted to prove a statement for all xA(x). ∀𝑥𝐴(𝑥) One way is to take an arbitrary x and show that it satisfies A(x). For example, to prove that for all n there is an m M bigger than n squared. 2 ∀𝑛∃𝑚(𝑚 > 𝑛 ) Let n be any natural number. Let m be the sum of n squared and 1. 2 𝑚 =𝑛 + 1 Then m is bigger than n squared. 𝑚 >𝑛 2 And this proves the statement there is an m, m bigger than n squared. 2 ∃𝑚(𝑚 > 𝑛 ) And it follows that the statement for all m there is an m bigger than n squared is true. 2 ∀𝑛∃𝑚(𝑚 > 𝑛 ) To prove a statement involving two quantifiers, such as "For every x, there exists an y such that y>x squared," we can eliminate one quantifier by replacing it with an arbitrary natural number. We must make no assumptions about this arbitrary number other than that it is a natural number. The argument will have to hold for any natural number whatsoever because we are trying to show that this is true for all natural numbers. Let's look at the logical reasoning behind this problem. In order to prove a statement involving two quantifiers of the form, for all n there is an m, we will eliminate one quantifier by replacing it with an arbitrary natural number. We will assume nothing about this number other than its status as a natural number. This is relevant because we are trying to show that this statement is true for all n; therefore, we must have an arbitrary number that fits our conditions. Then we can proceed with the proof by verifying that the rest of our formula still makes sense in light of our assumption. To prove for all x A(x), assume not all x A(x). This is equivalent to exist x not A(x). Well, let c be an object such that not A(c). Notice that this isn't an arbitrary object. It's a specific object, admittedly an object whose identity we may not know. But that doesn't matter: The point is to prove this universal statement, we began by assuming its negation. Its negation gives us an existential statement. And that tells us that there will be some object, a specific object, for which not A(c). Now that we have a starting point, we can derive a contradiction. We reason with the assumption that c is true together with the fact that not A(c) to derive a contradiction. Now, the exact reasoning you use will depend on what statement A says. But for this basic idea to work, you need to prove for all x A(x). So you assume not for all x A(x), which is equivalent to exist x not A(x). You must find an object at least knowing that an object exists for which not A(c). Then you can reason with that object using the fact that not A(c) to derive a contradiction. Now I'd like to give you a brief quiz so that you can see how much you've learned about different kinds of arguments. It is not valid to prove a statement by assuming it is true and showing that it leads to a contradiction. We've even stated what the value of p is (namely, some positive rational number), which is different from saying let p be arbitrary, because an arbitrary choice of p leads to a specific p (namely, the one we chose). Let p be arbitrary. Then, although the choice of p may have been arbitrary, once you've made it, p is specific. In contrast, when you argue with an arbitrary p, you do not know anything about that p. You certainly would not know that it was equal to .001 or whatever. Now let us examine the method of proof by induction. This is the case where we prove universal statements that involve the natural numbers. For example, to prove that 1 + 2 + etc., etc., etc., + n = a half n(n+1), we assume the statement to be true for all natural numbers less than or equal to n. 1+2 +… + 𝑛 = 1 2 (𝑛 + 1) So a natural question to ask is whether this formula is true for the first few cases. Given that 1 is the first natural number, you can verify by hand that 1 times 1 plus 1 equals 2, which indeed makes sense since the sum of the first two integers is indeed 2. 𝑛=1 Well then we just got 1 here I'm putting n equals 1 into the formula. We have half times 1 (1+1). Which is a half times 1 times 2 which is 1. And indeed 1 equals 1. 1= 1 2 . 1. (1 + 1) = 1 2 . 1. 2 = 1 So, it is true that in the first case, n=2. In the second case, n=2. What do we have? We have 1+2 on the left hand side, equals 2 on the right. A half times 2 (2+1), which is equal to 3. And 1+2 does equal 3. 1+2 = 1 2 . 2. (2 + 1) = 1 2 . 2. 3 = 3 So the formula is correct for n = 2. We might want to try n = 3. What do we get then? We get 1 + 2 + 3, Equals a half of 6 (3+1). Which is a half of 3 4 which is 6. 1+2 +3 = 1 2 1 2 . 3. (3 + 1) = . 3. 4 = 6 So far, this isn't proof. You need to check the first three cases, but doing so gives you some sense of what's going on. At this point, you still don't know if the formula checks out in general; you only know it checks out for a few cases. When calculating the formula p(n) = n2 + n + 41, be sure not to make the common mistake of jumping to conclusions. 2 𝑃(𝑛) = 𝑛 + 𝑛 + 41 The numbers 2, 3 and 5 are prime numbers. All values of p(n) for n equals to one, two, three etc. are multiples of these primes until you reach 41. When you get to 41, you'll find that P(41) works out at 1,681. This is because 41 squared equals 1,681. 2 𝑃(41) = 1681 = 41 Although it is not always a good idea to begin by working out a few cases, in this example it provides insight into the formula and can occasionally lead to the discovery of patterns. The numerical evidence here cannot be used to draw conclusions about all possible values of n. This example, due to the famous Swiss mathematician Leonard Euler in 1772, is a cautionary tale about jumping to conclusions based on numerical evidence. In the case of this function, there is no pattern to find. However, if you calculated more terms of the sequence such as n=4 or n=5, it would become apparent that these numbers are actually prime numbers. When we have established the validity of a formula for a few cases, we can then use it to prove a principle. The method of mathematical induction depends on a basic understanding of how the formula works. Suppose you want to prove that for any natural number n, if statement A(n) is true then statement A(n+1) is also true. Establish the following two statements: One, prove that A(1) is true; and two, prove that if A(n) is true then A(n+1) is also true. (∀𝑛)[𝐴(𝑛) ⇒ 𝐴(𝑛 + 1)] Suppose you want to prove a statement true for every natural number. That's known as the Induction step. Now intuitively, this gives the statement for all of n A(n) as follows. By the initial step, step one, A(1). If we now apply the induction step in the special case where n=1. We have A(1) by the initial step and that yields A(n+1) which is A(2). So by two, or by step two, A(1) yields A(2). 𝐴(1) ⇒ 𝐴(2) The argument employing mathematical induction can be explained intuitively as follows: if we assume that A(1) is true, then we can conclude that A(2) is true. We can then use the induction step on a special case: where n equals 1. Having proved this, we can conclude that A(3) is true by repeating the process all the way through the natural numbers. The falling of a domino is similar to the process of iteration. Now that we have laid out the method of mathematical induction, we will apply it to prove a theorem: for any natural number n, one plus two plus three plus n equals half n(n+1). 1+2 +3 + … +𝑛 = 1 2 𝑛(𝑛 + 1) We will use mathematical induction in this proof. Since one of the goals of a proof is to show why something is true, it is good form to indicate that that is the method I am using. So let us first show that the identity holds when n = 1 and then demonstrate that it holds for n + 1. To do this, consider n = 1. The identity reduces to (1)(1+1), which equals (1)(2) on the left-hand side and does equal (1)(2) on the right-hand side. 1= 1 2 (1)(1 + 1) = 1 2 (1)(2) Since both sides equal 1, we have proven the first step. In addition, you may have noticed that we referred to this as an identity, rather than an equation. Identities are not like equations because they do not contain variables that need to be solved for a variable value. The identity above states that the two sides are always equal. We use the word equation to refer to an expression that claims or states that two things are equal for all values of n. To prove the identity, we will assume that it holds for one integer value of n and then show that it also holds for the next integer value (n + 1). 1+2 +… + 𝑛 = 1 2 𝑛(𝑛 + 1) Deduce 1 + 2 +...+ (n + 1) = one-half (n + 1) ( n + 1) + 1. 1 + 2 + … + (𝑛 + 1) = 1 2 (𝑛 + 1)(𝑛 + 1) + 1) And the challenge now is to start with what we know and deduce where we want to get. How can we get this from that? Well, one way would be to add n + 1 to both sides of that identity. Which means, if we get the left-hand side here and then hope that when we work out the right-hand side having added n + 1. We end up with this expression. Let's add n + 1 to both sides of the star which is the identity we`re assuming; let us add n + 1 to both sides of the star. That gives us 1 + 2 +...+ n + (n + 1) = one half n(n+1)+(n+1). 1 + 2 + … + 𝑛 + (𝑛 + 1) = 1 2 𝑛(𝑛 + 1) + (𝑛 + 1) We can take n(n + 1) out as a common factor to get 1/2[n(n + 1) + 2(n + 1)]. This represents one-half of [n squared + n] plus 3n + 2. 1 + 2 + … + 𝑛 + (𝑛 + 1) = 1 2 𝑛(𝑛 + 1) + (𝑛 + 1) = 1 2 [𝑛(𝑛 + 1) + 2(𝑛 + 1)] = 1 2 [𝑛2 + 𝑛 + 2𝑛 + 2] = 1 2 2 [𝑛 + 3𝑛 + 2] And these factors. This is one-half (n + 1) (n + 2). = 1 2 [(𝑛 + 1)(𝑛 + 2)] But the same thing follows if we write the quantity as a one-half plus one. = 1 2 (𝑛 + 1)((𝑛 + 1) + 1) The identity holds for every integer n, by mathematical induction. We have proven that the identity holds for n=1 (a simple matter of observation). Next we prove that it holds for n=k+1, assuming it holds for k. By mathematical induction, the identity holds for all integers n. 2 𝑃(𝑛) = 𝑛 + 𝑛 + 41 The polynomial P(n) = n2 – n + 41 is a quadratic expression with integer coefficients. 2 𝑃(𝑛) = 𝑛 − 𝑛 + 41 We got the same result, and for this reason it's the case that for all values of the polynomial for n = 1, 2, 3, 4...all the way up through n = 40, it's prime. Then P(41). If you put that in, it's 41 squared- 41 + 41, which is 41 squared, which is this number here- 1,681. 2 𝑃−(41) = 41 (= 1681) Let us call that P sub- to indicate there's a minus sign here. Because the polynomial we want now, we'll call P + (n), was this one + n + 41. 2 𝑃+(𝑛) = 𝑛 + 𝑛 + 41 The number 40 is the only square that can be multiplied by itself and add 1 to produce a prime number. There are no other primes between 1 and 40, except for 1 and 2. And if we include 40 in this equation, we get 40 × 41 + 41. This means we have 41 lops of 41 which equals 1681. 𝑃+(40) = 40(40 + 1) + 41 = 40. 41 + 41 2 = 41 = 1681 When you look at the behavior of these two polynomials, they are essentially identical.