Understanding Mathematical Induction for Primes

Proofs with Quantifiers Where are the correct answers? Suppose it can be proved that there is a positive real number x such that, for any natural number n greater than 1, 1 + x to the n + 1 is bigger than 1 + (n + 1) x. Then we can prove the following theorem: if x is a positive real number and n is any natural 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 the statement is true for n = 0, then assuming it is true for n = k (with k a given natural number), 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 bigger than 1+2x. 2 (1 + 𝑥) > 1 + 2𝑥 Here, we set n equal to 1. The sum of (1 + x)2 is larger than 1 + 2x by the binomial theorem, which tells us that (1 + x)2 is equal to 1 + 2x + x2, which is greater than 1 + 2x. 2 2 (1 + 𝑥) − 1 + 2𝑥 + 𝑥 > 1 + 2𝑥 Because x squared is strictly positive. Notice that x is positive, so in particular, x is nonzero. 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) implies A(n+1). ∀𝑛[𝐴(𝑛)⇒𝐴(𝑛 + 1)] Since the expression x squared is positive, it follows that x squared is strictly positive. Since x is nonzero and positive, in particular, x squared is positive. Hence that 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 equal to (1+x) to the n+1. From this assumption, we can deduce that 1+x is greater than or equal to (1+x) to the n+2. We will begin by focusing on the first expression in parentheses. (1 + 𝑥) 𝑛+2 𝑛+1 = (1 + 𝑥)91 + 𝑥) And by the induction hypothesis, (1+x) to the n+1 is bigger than 1+(n+1)x. (1 + 𝑥) 𝑛+2 𝑛+1 = (1 + 𝑥)91 + 𝑥) > (1 + 𝑥)[1 + (𝑛 + 1)𝑥] And that equals 1 + (n+1)x+x+(n+1)x squared. (1 + 𝑥) 𝑛+2 𝑛+1 = (1 + 𝑥)91 + 𝑥) = 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 bigger than 1 + (n+2)x. (1 + 𝑥) 𝑛+2 𝑛+1 = (1 + 𝑥)91 + 𝑥) 2 = 1 + (𝑛 + 2)𝑥 + (𝑛 + 1)𝑥 > 1 + (𝑛 + 2)𝑥 To prove a statement true for all natural numbers, first prove it for 1, and then give a conditional proof—an induction step—to show that if the statement is true for some specific 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. This is done by assuming A(n) and then deducing A(n+1) from it. It typically involves looking 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 that each term within the sequence satisfies this assumption. In conclusion, by the principle 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 the number 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 when we are trying to prove something of this form that A(1) is false. The reason we have a n0 as the starting point is precisely because the result does not hold at the beginning: General induction starts at one and this variant starts at some point beyond 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 states every natural number greater than 1 can be written as a product of prime numbers. A prime number is a positive integer greater than 1 whose only two positive integral divisors are 1 and itself. The integer 0 is not properly used as a number; it is an integer but not a natural number, since the first natural numbers are 1, 2, 3, and so on. 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 of primes. 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 >= 2 in our proof. The induction step of the mathematical proof relies on the following statement: If a number m is less than or equal to n and n is less than or equal to 2m, then m is either 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 must start with its base case, which establishes that for any natural number less than or equal to 2, all other natural numbers between it and n are composite (are divisible by 1 or themselves). So let's look at what it says when m = 2: if m = 2 then there is only one composite number between 2 and n; all the other numbers between 2 and n are primes. 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 to 3 (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 natural numbers 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. This means that if n+1 is not prime, it can be written as the product of two smaller integers. However, since 2 less than or equal to p and q less than or equal to n are either primes or products of primes, by A(n) p and q are either primes or products of primes. 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 by induction. When we look at this proof, we can see why it is important to formulate our inductive hypothesis as we have. By assuming that each number from 1 to n is either prime or composed of primes, we can conclude that n + 1 and m + 1 are either prime or composed of primes as well. The principle of induction is a fundamental principle of mathematics. Indeed, if we can always go one more step, then we will eventually reach every natural number. It requires a lot of effort to construct an induction proof, but you should try your hand at assignment eight.