Lecture Note
University
Stanford UniversityCourse
Introduction to Mathematical ThinkingPages
6
Academic year
2022
Murphyal
Views
31
Proofs with Quantifiers The method of induction is a general process for proving statements about all naturalnumbers by first proving that the statement holds for one specific number x, and thenusing that fact to show that it then holds for all natural numbers. This method of proofbuilds on smaller cases and uses them to prove larger cases, hence the nameinduction, which means "to build up." But first, let's look at how we might prove anexisting statement. βπ₯π΄(π₯) To prove that there are irrational numbers r and s such that r to the power s isrational, one considers two cases: if , then r = s = 2; otherwise, case 1: if can beexpressed as the ratio of two cubes, r = ks where k is an integer. Because (2)2 iseven 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 rsatisfying. πΌπ 2 2 ππ πππ‘πππππ, π‘πππ π = π = 2 If the square root of 2 is rational, then there are numbers r and s such that r to thepower s is rational. If this assumption is not true, then we must assume that thesquare root of 2 is irrational. In this case, take the square root of 2 and set it equal tos. πΌπ 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 2which 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 sto 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 thecase. Instead, we look at both cases and take different irrationals r and s for eachcase. By choosing r to the s to be rational in one case and irrational in the other, weare 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 universalquantifier. 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, toprove 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 any such that y>x squared," we can eliminate one quantifier by replacing it with anarbitrary natural number. We must make no assumptions about this arbitrary numberother than that it is a natural number. The argument will have to hold for any naturalnumber whatsoever because we are trying to show that this is true for all naturalnumbers. 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 anm, 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 canproceed with the proof by verifying that the rest of our formula still makes sense inlight 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'sa specific object, admittedly an object whose identity we may not know. But thatdoesn't matter: The point is to prove this universal statement, we began by assumingits negation. Its negation gives us an existential statement. And that tells us thatthere 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 theassumption 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 thisbasic 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 thatan object exists for which not A(c). Then you can reason with that object using thefact 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 learnedabout different kinds of arguments. It is not valid to prove a statement by assuming it is true and showing that it leads toa contradiction. We've even stated what the value of p is (namely, some positiverational number), which is different from saying let p be arbitrary, because anarbitrary 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, onceyou've made it, p is specific. In contrast, when you argue with an arbitrary p, you donot 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 thecase where we prove universal statements that involve the natural numbers. Forexample, to prove that 1 + 2 + etc., etc., etc., + n = a half n(n+1), we assume thestatement to be true for all natural numbers less than or equal to n. 1 + 2 + β¦ + π = 12 (π + 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 1equals 2, which indeed makes sense since the sum of the first two integers is indeed2. π = 1 Well then we just got 1 here I'm putting n equals 1 into the formula. We have halftimes 1 (1+1). Which is a half times 1 times 2 which is 1. And indeed 1 equals 1. 1 = 12 . 1. 1 + 1 ( ) = 12 . 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), whichis equal to 3. And 1+2 does equal 3. 1 + 2 = 12 . 2. 2 + 1 ( ) = 12 . 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 = 12 . 3. 3 + 1 ( ) = 12 . 3. 4 = 6 So far, this isn't proof. You need to check the first three cases, but doing so gives yousome sense of what's going on. At this point, you still don't know if the formulachecks out in general; you only know it checks out for a few cases. When calculatingthe formula p(n) = n2 + n + 41, be sure not to make the common mistake of jumpingto 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. π 41 ( ) = 1681 = 41 2 Although it is not always a good idea to begin by working out a few cases, in thisexample it provides insight into the formula and can occasionally lead to thediscovery of patterns. The numerical evidence here cannot be used to drawconclusions about all possible values of n. This example, due to the famous Swissmathematician Leonard Euler in 1772, is a cautionary tale about jumping toconclusions based on numerical evidence. In the case of this function, there is no pattern to find. However, if you calculatedmore terms of the sequence such as n=4 or n=5, it would become apparent thatthese numbers are actually prime numbers. When we have established the validity of a formula for a few cases, we can then useit to prove a principle. The method of mathematical induction depends on a basicunderstanding of how the formula works. Suppose you want to prove that for anynatural 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, provethat 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 knownas the Induction step. Now intuitively, this gives the statement for all of n A(n) asfollows. By the initial step, step one, A(1). If we now apply the induction step in thespecial 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 asfollows: if we assume that A(1) is true, then we can conclude that A(2) is true. Wecan 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 throughthe 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 toprove a theorem: for any natural number n, one plus two plus three plus n equalshalf n(n+1). 1 + 2 + 3 + β¦ + π = 12 π(π + 1) We will use mathematical induction in this proof. Since one of the goals of a proof isto show why something is true, it is good form to indicate that that is the method I amusing. So let us first show that the identity holds when n = 1 and then demonstratethat 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-handside. 1 = 12 1 ( ) 1 + 1 ( ) = 12 (1)(2) Since both sides equal 1, we have proven the first step. In addition, you may havenoticed that we referred to this as an identity, rather than an equation. Identities arenot like equations because they do not contain variables that need to be solved for avariable value. The identity above states that the two sides are always equal. We use the wordequation to refer to an expression that claims or states that two things are equal forall values of n. To prove the identity, we will assume that it holds for one integervalue of n and then show that it also holds for the next integer value (n + 1). 1 + 2 + β¦ + π = 12 π(π + 1) Deduce 1 + 2 +...+ (n + 1) = one-half (n + 1) ( n + 1) + 1. 1 + 2 + β¦ + π + 1 ( ) = 12 π + 1 ( ) π + 1 ( ) + 1) And the challenge now is to start with what we know and deduce where we want toget. How can we get this from that? Well, one way would be to add n + 1 to bothsides of that identity. Which means, if we get the left-hand side here and then hopethat when we work out the right-hand side having added n + 1. We end up with thisexpression. Let's add n + 1 to both sides of the star which is the identity we`reassuming; 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 ( ) = 12 π π + 1 ( ) + (π + 1) We can take n(n + 1) out as a common factor to get 1/2[n(n + 1) + 2(n + 1)]. Thisrepresents one-half of [n squared + n] plus 3n + 2. 1 + 2 + β¦ + π + π + 1 ( ) = 12 π π + 1 ( ) + π + 1 ( ) = 12 π π + 1 ( ) + 2 π + 1 ( ) [ ]
= 12 π 2 + π + 2π + 2 [ ] = 12 [π 2 + 3π + 2] And these factors. This is one-half (n + 1) (n + 2). = 12 [ π + 1 ( ) π + 2 ( )] But the same thing follows if we write the quantity as a one-half plus one. = 12 (π + 1)( π + 1 ( ) + 1) The identity holds for every integer n, by mathematical induction. We have proventhat the identity holds for n=1 (a simple matter of observation). Next we prove that itholds for n=k+1, assuming it holds for k. By mathematical induction, the identityholds 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 thepolynomial for n = 1, 2, 3, 4...all the way up through n = 40, it's prime. Then P(41). Ifyou put that in, it's 41 squared- 41 + 41, which is 41 squared, which is this numberhere- 1,681. π β 41 ( ) = 41 2 (= 1681) Let us call that P sub- to indicate there's a minus sign here. Because the polynomialwe 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 toproduce a prime number. There are no other primes between 1 and 40, except for 1and 2. And if we include 40 in this equation, we get 40 Γ 41 + 41. This means wehave 41 lops of 41 which equals 1681. π + 40 ( ) = 40 40 + 1 ( ) + 41 = 40. 41 + 41 = 41 2 = 1681 When you look at the behavior of these two polynomials, they are essentiallyidentical.
Mathematical Induction Explained: Study Guide
Please or to post comments