Proof Methodologies PDF

Week 2 Reading Material ======================= More Proof Methodologies! ------------------------- Proof by contradiction:\ \ [Method]: 1. Consider the given mathematical statement as a propositional statement p and consider that \~p is true. 2. By the end of the proof, we intend to show...

Week 2 Reading Material ======================= More Proof Methodologies! ------------------------- Proof by contradiction:\ \ [Method]: 1. Consider the given mathematical statement as a propositional statement p and consider that \~p is true. 2. By the end of the proof, we intend to show that \~p -\> F is true, where F is always false. 3. This case is only possible when \~p is false. If negation p were false then that means p is true. [Example]: Prove that √2 is Irrational [Proof]: 1. Consider that the given mathematical statement is p: "√2 is Irrational" and let us consider the negation of it \~ p: "√2 is Rational" If √2 is rational then there exists two integers a and b such that √2 = a/ b Let us assume that a and b do not have any common factors i.e, both a and b are not even. (the fraction a/ b is in the simplest form). If we square on both sides of the expression, we have 2 = a^2^/ b^2^ - 2 b^2^ = a^2^ - Here, if we consider the value of a^2^, then we can clearly see that it is of the form 2 multiplied to some integer b^2^ - a^2^ is even - Whenever, a^2^ is even, a is even. - 2 b^2^ = (2k)^2\ ^ - 2 b^2^ = 4k^2^ - b^2^ = 2k^2^ - Here, b^2^ is of the form 2 multiplied to some integer k^2^ - b^2^ is even. - b is even. Existence Proof: ---------------- 1. Constructive Existence Proof: Consider the following values for a, b, and c respectively. a = 3, b = 4, c = 5 LHS: a^2^ + b^2^ - 32 + 42 = 9 + 16 = 25 RHS: c^2^ C^2^ = 5^2^ = 25 Here, we can clearly see that LHS = RHS Therefore, we can say that there exists values of a, b, and c such that the statement a^2^ + b^2^ = c^2^ is true. [Note]: We can also prove this mathematical statement using any of the Pythagorean Triples like (a, b, c) = (6, 8, 10); (5, 12, 13); etc... 2. Non-constructive Existence Proof: We try to prove the predicate P(x) without providing a specific example or algorithm for it. We try to show that an instance exists for proving the statement indirectly. [Example]: There exist irrational numbers x, y such that x^y^ is rational. [Proof]: Assume that x = √2 and y = √2 x^y^ = (√2) √2 Here, there are two possibilities i.e., this value could be rational/ irrational. If (√2) √2 is a rational number, then the proof completes here. [Case 2]:\ \ If (√2) √2 is Irrational, Then we will update the values such that x = (√2) √2 and y = √2 Let us evaluate the value of x^y^ now. - x^y^ = (√2^√2^) ^√2^ = √2^√2.√2^ = (√2)^2^ = 2. - Here, 2 is rational Proof By Cases: --------------- It a proof methodology used to demonstrate a statement/ predicate is true by splitting the problem into parts that are considered/ evaluated separately which are called as cases. Method: ------- [Step 1]: Show that there are a set of cases that are mutually exhaustive.\ \ [Step 2]: Prove that the statement is true in each of the provided cases. [Example]: For any integer k, the result of 3k^2^ + k is even. [Step 1]: Consider the possible cases. Here, the mathematical statement deals with the notion of the result being an even number. So, we can think of the cases wherein k is an even number and the case wherein k is an odd number. - Case 1: k is even. - Case 2: k is odd. [Step 2]: Proving the statement for the considered cases. [Case 1]: If k is even - k can be expressed as k = 2p - 3k^2^ + k = 3 (2p)^2^ + (2p) = 3 (4p^2^) + 2p = 12p^2^ + 2p - Here, 12 p^2^ + 2p can be expressed as 2 (6p^2^ + p) this is of the form of 2 multiplied to some integer 6p^2^ + p - 3k^2^ + k is in the form of an even number. [Case 2]: If k is odd - K can be expressed as k = 2p + 1 - 3k^2^ + k = 3 (2p + 1)^2^ + (2p + 1) = 3 (4p^2^ + 4p + 1) + 2p + 1\ = 12p^2^ + 12p + 3 + 2p + 1 = 12p^2^ + 14p + 4 = 2 (6p^2^ + 7p + 2) This is of the form of 2 multiplied to some integer 6p^2^ + 7p + 2 - 3k^2^ + k is in the form of an even number. Counter Example: ---------------- To show that a statement of the form of a universally quantified predicate is false, we need only one example/ instance and it is called as a counter example for the predicate/ statement. [Example]: Consider the following mathematical statement: "All prime numbers are odd." Here, if we consider the prime number to be 2, then this serves as a counter example to the above statement as 2 is an even prime number. Fallacy: -------- An instance of improper reasoning leading to an unexpected result that is false is called as a fallacy. Fallacies are usually encountered due to incorrect application of rules of logic. [Example]: Consider the following arguments: p -\> q: "If you do every problem in this book, then you will learn discrete mathematics." q: "You learned discrete mathematics." ∴ p: "you did every problem in this book."\ \ How can we check the consistency/ validity of an argument? (alternative method) We can express the set of arguments and conclusions in the form of a compound proposition ((p -\> q) ∧ q) -\> p If the arguments and conclusion are valid, then the truth table for the above expression must be a tautology. **p** **q** **(((p → q) ∧ q) → p)** ------- ------- ------------------------- F F **T** F T **F** T F **T** T T **T** Here, we can clearly see that the truth values of above compound expression is not a tautology. Therefore, the above argument and conclusion is a fallacy. Mathematical Induction (Weak Induction): ---------------------------------------- Mathematical Induction is a technique of proving a statement, theorem or formula which is thought to be true, for each and every natural number n. By generalizing this in form of a principle which we would use to prove any mathematical statement is 'Principle of Mathematical Induction'. [Method]: **Step 1: ** Check whether the given statement is true for n = 1 (or) the base case given. **Step 2: **Assume that given statement P(n) is also true for n = k, where k is any positive integer. **Step 3: ** Prove that the result is true for P(k+1) for any positive integer k. If the above-mentioned conditions are satisfied, then it can be concluded that P(n) is true for all n natural numbers from the base case. [Example]: For any positive integer number n, prove that n^3^ + 2n is always divisible by 3 [Proof]: Let P(n): n3 + 2n is divisible by 3 be the given statement. [Step 1]: Basic Step Firstly we prove that P(1) is true. Let n = 1 in n^3^ + 2n = 1^3^ + 2(1) = 3 As 3 is divisible by 3. Hence, P(1) is true. [Step 2]: Assumption Step Let us assume that P(k) is true Then, k^3^ + 2k is divisible by 3 Thus, we can write it as k^3^ + 2k = 3n (where n is any positive integer)....(i) [Step 3]: Induction Steps Now we have to prove that algebraic expression (k + 1)^3^ + 2(k + 1) is divisible by 3 = (k + 1)^3^ + 2(k + 1) = k^3^ + 3k^2^ + 5k + 3 = (k^3^ + 2 k) + (3k^2^ + 3k + 3) from eq(i) = 3n + 3(k^2^ + k + 1) = 3(n + k^2^ + k + 1) As it is a multiple of 3 we can say that it is divisible by 3. Thus, P(k+1) is true i.e. (k + 1)^3^ + 2(k + 1) is be divisible by 3. Now by the Principle of Mathematical Induction, we can say that, P(n): n3 + 2n is divisible by 3 is true. Strong Induction: ----------------- Proof by strong induction is a mathematical technique for proving universal generalizations. It differs from ordinary mathematical induction (also known as weak mathematical induction) with respect to the inductive step. In a weak mathematical induction, the inductive step involves showing that if some element n has a property, then the successor element n + 1 must also have that property. In a strong mathematical induction, the inductive step involves showing that if all elements up to and including n have some property, then n + 1 has that property as well. [Method]: **Step 1: Basis Step:** We prove that P(1) is true or the base case is true. **Step 2:** **Induction Hypothesis:** P(1) \^ P(2) \^... \^ P(k) is true **Step 3:** **Inductive Step:** If P(1) \^ P(2) \^... \^ P(k) is true for arbitrary k, We show that P(k + 1) is true. Example: For any positive integer n, greater than 1, n can be written as the product of one or more prime numbers. [Proof:] By strong induction, - Here, the domain is the set of positive integers greater than 1 - Integers greater than or equal to 2. 1. [Basis Step:] We show that P(2) is true Since 2 is a prime number, it can be written as a product of itself. Therefore, P(2) is true. 2. [Inductive Hypothesis:] Assume that P(2) \^... P(k) is true. 3. [Inductive step:] Consider the number (k+1) Here, we can intuitively think of two possibilities i.e, k+1 being a prime number or a composite number. Case 1: If k + 1 is prime, - k + 1 can be written as the product of itself. Therefore, k +1 is true for this case. Case 2: If k + 1 is composite, - k + 1 can be written as the product of two numbers - (k + 1) = a x b; such that 1 \< a \ common difference. (difference of any two consecutive terms in the series) - n^th^ term of an Arithmetic progression is given by a~n~ = a + (n -- 1) d - The sum of n terms of an AP is calculated by S~n~ = n/2 \[2a + (n -- 1) d\] (or) n/2\[ a + l\] Where, n -\> number of terms a -\> first term d -\> common difference. S~n~ -\> Sum of n terms l -\> Last term of the sequence. Harmonic Progression: --------------------- A sequence of the form 1/a, 1/a + d, 1/ a + 2d,.... Is called as a Harmonic Progression. [Note:] If h~1~, h~2~,..., h~n~ are the terms of a harmonic progression, then 1/h~1~, 1/h~2~,.... Form the terms of an Arithmetic Progression. Geometric Progression: ---------------------- A sequence of the form a, ar, ar^2^, ar^3^,... ar^n^ is called as a geometric progression. Where, a -\> first term. r = a~2~/ a~1~-\> common ratio (ratio of two consecutive terms in the sequence) The n^th^ term of a GP is given by a~n~ = ar^n\ --\ 1^ The sum of n terms of a GP is given by S~n~ = a(1 -- r^n^)/(1 -- r) (if 1 \> r) S~n~ = a (r^n^ - 1)/(r - 1) (if 1 \< r) The sum of infinite terms of a GP is given by a/1 - r