Mathematical Proof Techniques and Examples
Explore various proof techniques in mathematics including direct proofs, proofs by cases, proofs by contrapositive, and examples showing how to prove statements using algebra, definitions, and known results. Dive into proofs involving integers, even and odd numbers, and more to enhance your understanding of mathematical reasoning.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Direct Proof To prove: if something, then this other thing 1. Something 2 . reason using definitions, algebra, known results as reason assumption X. This other thing last statement using above X+1. if something, then this other thing. 1-X
Prove: If x Q ^ y Q, then x+y Q 1. x Q ^ y Q 2. x = a/b, a Z, b Z, b!=0 3. y = c/d, c Z, d Z, d!=0 4. x + y = a/b + c/d 5. x + y = ad/bd + bc/bd 6. x + y = (ad + bc)/bd 7. ad + bc Z 8. bd Z 9. x + y Q 10.If x Q ^ y Q, then x+y Q assumption def Q def Q 2, 3, substitution 4, algebra, b,d != 0 5, algebra sum and product of integers are integers product of integers is an integers 6,7,8 definition of Q 1-9
Proof with cases. (often part of a larger proof) To prove: if this or that, then the other thing 1. This or that assumption 2. Case 1: this since one or the other is true 3 reason using definitions, algebra, other results etc 4. The other thing last reason for this case 5. Case 2: that if not this, then that is true 6 . reason using definitions, algebra, other results etc 7. The other thing last reason for that case 8. if this or that, then the other thing 1-7 since one of the cases must be true
If a is even or b is even, then ab is even 1. a is even or b is even 2. Case 1: a is even 3. a = 2c 4. ab = 2cb 5. ab is even 6. Case 2: b is even 7. b = 2d 8. ab = a(2d) = 2ad 9. ab is even 10.If a is even or b is even, then ab is even. 1-8 since one case must be true assumption 1 definition of even 3, substitution 4, definition of even if not case 1, then case 2 is true definition of even 7, substitution, algebra 8, definition of even
Proof by contrapositive To prove: if something, then this other thing 1. Not this other thing 2 . reason using definitions, algebra, known results as reasons X. Not something X+1. if not this other thing, then not something X+2. if something, then this other thing assumption last in the sequence with such reasons 1-X X+1, contrapositive
If 2n4+ n + 5 is odd, then n is even 1. n is not even 2. n = 2k + 1, integer k 3. 2n4+ n + 5 = 2n4+ 2k + 1 + 5 4. 2n4+ n + 5 = 2(n4+ k + 3) 5. n4+ k + 3 is an integer 6. 2n4+ n + 5 is even (not odd) 7. If not(n is even), then not(2n4+ n + 5 is odd) 8. If 2n4+ n + 5 is odd, then n is even Assumption definition of even 2, substitution simplification, factoring sums and products of int are ints 4,5 definition of even/odd 1-6 7, contrapositive
Proof by contradiction To prove: something 1. Not something 2 . Reason using definitions, etc 3. Contradiction (usually p and not p) last statement from the reasoning 4. Something by contradiction (since (not something) => contradiction, not something must be false) Example: Prove Sqrt(2) is irrational. (see previous notes)
Proof using existential specification and universalization If x S, (P(x) ^ Q(x), then ( x S, P(x) ) ^ ( x S, Q(x) ) 1. x S, (P(x) ^ Q(x) 2. There is an a in S with P(a) ^ Q(a) 3. P(a) 4. x S, P(x) 5. Q(a) 6. x S, Q(x) 7. ( x S, P(x) ) ^ ( x S, Q(x) ) 8. If x S, (P(x) ^ Q(x), then ( x S, P(x) ) ^ ( x S, Q(x) ) assumption existential specification 2, rule p^q => p existential universalization 2, rule p^q => q existential universalization 4, 6 conjunction 1-7 Note, the converse is not true (why?)
Proof by induction To prove For all n >= n0, P(n) 0. base case: show true for a specific n0often 0 or 1, but could be any. 1. Assume P(n-1) 2. Reason using definitions, algebra, etc X. P(n). Last step in this reasoning X+1. P(n-1) => P(n) steps 1-X X+2. For all n >= n0, P(n) 0, X+1, induction
Lets try another P(n) is nk=02k= 2n+1 1 0. P(0) is 0k=02k= 20+1 1, the left side is 20= 1, the right side is 20+1 1 = 2 -1 = 1 So P(0) is true. Now we must prove P(n-1) => P(n) 1. Assume P(n-1) which is n-1k=02k= 2(n-1)+1 1 = 2n 1 2. nk=02k= n-1k=02k+ 2n 3. nk=02k= 2n 1 + 2n = 2*2n-1 4. nk=02k= 2n+1 1 5. P(n-1) => P(n) 6. For all n >= 0, nk=02k= 2n+1 1 def nk=02k 1, substitution 3, simplification 1-4 0, 5, induction
Strong induction Strong induction differs from induction by requiring for the induction hypothesis that P(k) is true for all n0<=k < n, then proving P(n). There may be a need for more than one base case, as there was for the Fibonnacci number question. Otherwise the structure of the proof is the same.
For any integer n>=1, p1, p2, p3, pk , all prime such that n = p1 p2p3 pk = ki=0 pi(call this P(n)) Proof by strong induction. 0. Base case: 1 = product of no primes (empty product is 1), so P(1) 1.assume for all x, 1<=x < n, x is the product of primes. P(x) all 1 <=x<n Case 1: n is prime, then n = n a prime so P(n). Case 2: n is not prime. 2.Then a,b, 1<a<n, 1<b<n, n = ab 3.a = q1 q2q3 qland b = r1 r2r3 rmwhere qi, rjare prime assumption 1 4. n = q1 q2q3 qlr1 r2r3 rm 5. (1<=x < n: P(x)) => P(n) 6. n Z+, P(n) def prime 2,3 substitution 1-4 0,5, strong induction
