Lecture Note
University
Stanford UniversityCourse
Introduction to Mathematical ThinkingPages
4
Academic year
2023
Murphyal
Views
52
Proofs with Quantifiers Where are the correct answers? Suppose it can be proved that there is a positive real number x such that, for anynatural number n greater than 1, 1 + x to the n + 1 is bigger than 1 + (n + 1) x. Thenwe can prove the following theorem: if x is a positive real number and n is anynatural number greater than 1, then x to the n + 1 is bigger than x to the n. (1 + π₯) π+1 > 1 + π + 1 ( )π₯ We will prove that for all natural numbers n, 1 + (n + 1 x) β₯ 1 + x by showing how thestatement is true for n = 0, then assuming it is true for n = k (with k a given naturalnumber), and showing that it logically follows that it must be true for n = k +1. (1 + π₯) π+1 > 1 + π + 1 ( )π₯ Well, the first step is to prove A(1). And A(1) is the statement. 1+x squared is biggerthan 1+2x. (1 + π₯) 2 > 1 + 2π₯ Here, we set n equal to 1. The sum of (1 + x)2 is larger than 1 + 2x by the binomialtheorem, which tells us that (1 + x)2 is equal to 1 + 2x + x2, which is greater than 1 +2x. (1 + π₯) 2 β 1 + 2π₯ + π₯ 2 > 1 + 2π₯ Because x squared is strictly positive. Notice that x is positive, so in particular, x isnonzero. Hence x squared is strictly positive. Hence that expression is strictly bigger
than 1 + 2x. So A(1) is true. The induction step Involves proving for all n, A(n) impliesA(n+1). βπ[π΄ π ( )βπ΄ π + 1 ( )] Since the expression x squared is positive, it follows that x squared is strictlypositive. Since x is nonzero and positive, in particular, x squared is positive. Hencethat expression is strictly greater than 1 + 2x. Thus A(1) is true. To prove that A(n)implies A(n+1), we assume that A(n) is true and prove that A(n+1) must be true. (1 + π₯) π+1 > 1 + π + 1 ( )π₯ And A(n+1) is the statement 1 + x to the n + 2 is greater than 1 + n plus 2x. (1 + π₯) π+2 > 1 + π + 2 ( )π₯ The induction step can be stated as follows: assume that 1+x is greater than or equalto (1+x) to the n+1. From this assumption, we can deduce that 1+x is greater than orequal to (1+x) to the n+2. We will begin by focusing on the first expression inparentheses. (1 + π₯) π+2 = 1 + π₯ ( )91 + π₯) π+1 And by the induction hypothesis, (1+x) to the n+1 is bigger than 1+(n+1)x. (1 + π₯) π+2 = 1 + π₯ ( )91 + π₯) π+1 > 1 + π₯ ( )[1 + π + 1 ( )π₯] And that equals 1 + (n+1)x+x+(n+1)x squared. (1 + π₯) π+2 = 1 + π₯ ( )91 + π₯) π+1 = 1 + π + 1 ( )π₯ + π₯ + (π + 1)π₯ 2 Which equals 1 plus we've got (n+1)x and another x, so altogether we've got(n+2)x + (n+1)x squared, and this is positive. So that expression is strictly biggerthan 1 + (n+2)x. (1 + π₯) π+2 = 1 + π₯ ( )91 + π₯) π+1 = 1 + π + 2 ( )π₯ + π + 1 ( )π₯ 2 > 1 + π + 2 ( )π₯ To prove a statement true for all natural numbers, first prove it for 1, and then give aconditional proofβan induction stepβto show that if the statement is true for somespecific value of n, then it must be true for the next natural number, n+1. π΄(π)βπ΄(π + 1) Mathematical induction is a method of proof in which A(n) is proven for every n. Thisis done by assuming A(n) and then deducing A(n+1) from it. It typically involveslooking at the form of A(n+1), manipulating it into such a form that you can apply A(n)
in order to carry out an argument, and then proving the theorem by showing thateach term within the sequence satisfies this assumption. In conclusion, by theprinciple of mathematical induction, this proves for all n greater than or equal to n0. βπβ₯π 0 ( ) π΄(π) Here, n0 is a number that we choose. For example, n0 might be the number 1, or thenumber 5, or the number 10 or any other number that we decide upon. Once again,it is important to note that A(1) might not be true. In fact, it is usually the case whenwe are trying to prove something of this form that A(1) is false. The reason we havea n0 as the starting point is precisely because the result does not hold at thebeginning: General induction starts at one and this variant starts at some pointbeyond one. But other than that, the argument's essentially the same: In particular,the induction step would be to prove for all numbers greater than or equal to n0 ,A(n) implies A(n+1). βπβ₯π 0 ( ) [π΄ π ( )βπ΄ π + 1 ( )] The Fundamental Theorem of Arithmetic is a result in number theory that statesevery natural number greater than 1 can be written as a product of prime numbers. Aprime number is a positive integer greater than 1 whose only two positive integraldivisors are 1 and itself. The integer 0 is not properly used as a number; it is aninteger but not a natural number, since the first natural numbers are 1, 2, 3, and soon. Here is the part of the Fundamental Theorem of Arithmetic that needs to be proven.It is this theorem: Every natural number greater than 1 is either prime or a product ofprimes. We will use a variant of induction for this one because it's not true for n = 1.In fact, one is the only number for which it doesn't hold. So we have to start at n >= 2in our proof. The induction step of the mathematical proof relies on the following statement: If anumber m is less than or equal to n and n is less than or equal to 2m, then m iseither prime or a product of primes. βπ[2β€πβ€πβπ ππ πππ‘βππ π πππππ ππ π πππππ’ππ‘ ππ ππππππ ] The Prime Number Theorem states that when moving through the natural numbers,certain numbers are prime or the product of primes. To prove this theorem, we muststart with its base case, which establishes that for any natural number less than orequal to 2, all other natural numbers between it and n are composite (are divisible by1 or themselves). So let's look at what it says when m = 2: if m = 2 then there is onlyone composite number between 2 and n; all the other numbers between 2 and n areprimes. Because this statement holds true for any value of m less than or equal to n+ 1, we can assume that it also holds true for all values of m greater than or equal to3 (since it would be illogical to assume otherwise). 2β€πβ€π + 1 If m is less than or equal to n + 1, then m is either a prime or a product of primes.The only other possibility is that m equals n + 1. If n + 1 is prime, then m is also
prime. So what happens if m = n + 1 and n + 1 is not prime? Then there are naturalnumbers p and q such that 1 less than p, q less than n +1, and n +1 = pq. 1 < π, π < π + 1 πππ π + 1 = ππ If n+1 is not prime, it can be obtained as a product of two smaller numbers. Thismeans that if n+1 is not prime, it can be written as the product of two smallerintegers. However, since 2 less than or equal to p and q less than or equal to n areeither primes or products of primes, by A(n) p and q are either primes or products ofprimes. 2β€π, πβ€π, ππ¦ π΄ π ( ), π, π Two numbers, p and q, are less than or equal to n + 1 and thus are less than n.Since A(n), each of these numbers is either a prime or a product of primes. Since n +1 is a product of them, it must be a product of primes. The theorem follows byinduction. When we look at this proof, we can see why it is important to formulate our inductivehypothesis as we have. By assuming that each number from 1 to n is either prime orcomposed of primes, we can conclude that n + 1 and m + 1 are either prime orcomposed of primes as well. The principle of induction is a fundamental principle of mathematics. Indeed, if wecan always go one more step, then we will eventually reach every natural number. Itrequires a lot of effort to construct an induction proof, but you should try your hand atassignment eight.
Understanding Mathematical Induction for Primes
Please or to post comments