Mathematical Induction in Discrete Mathematics
Today's topics cover proof by induction in Section 3.6, outlining its use in proving theorems for all integers. Examples and a template are provided for better understanding. Get ready to explore the concept further!
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Clicker frequency: CA CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/
Todays topics Proof by induction Section 3.6 in Jenkyns, Stephenson
Mathematical induction Useful for proving theorems of the form: For all integers n >= a, P(n). a is some integer (usually 0, 1, or 2, but could be anything) P(n) is some predicate statement using n Examples: For all integers n >= 1, the sum of the integers from 1 to n (inclusive) is ?(?+1) 2 Any set of size n has 2nsubsets For all prices p >= 8 cents, the price p can be paid using only 5- cent and 3-cent coins. .
Mathematical induction For all integers n >= a, P(n). Base case - push first domino Inductive step nth domino pushes the n+1th
Example Theorem: for all ? 1, the sum of the integers from 1 to n (inclusive) is equal to ? ?+1 2 . In mathematical notation: ? ? =? ? + 1 2 ?=1 How should a proof by induction look like? Two steps: Base step (first n where it s true, in this case n=1) Inductive step (show that if true for any n, then it is true for n+1)
Proof by induction template ? =? ?+1 ? Theorem: ?=1 2 Proof (by mathematical induction): Base step: Show the theorem holds for n=____. ____________________________________________ Inductive step: Assume [or Suppose ] that __________________. WTS: ____________________. _____________________________________________ _____________________________________________ _____________________________________________ So the inductive step holds, completing the proof.
Proof by induction template ? =? ?+1 ? Theorem: ?=1 2 Proof (by mathematical induction): Base step: Show the theorem holds for n=____. ____________________________________________ Inductive step: Assume [or Suppose ] that __________________. WTS: ____________________. _____________________________________________ _____________________________________________ _____________________________________________ So the inductive step holds, completing the proof. A.1 B.2 C.n D.n+1 E.Other
Proof by induction template ? =? ?+1 ? Theorem: ?=1 2 Proof (by mathematical induction): Base step: Show the theorem holds for n=1. 1 =1 1 + 1 2 Inductive step: Assume [or Suppose ] that __________________. WTS: ____________________. _____________________________________________ _____________________________________________ _____________________________________________ So the inductive step holds, completing the proof.
Proof by induction template ? =? ?+1 ? Theorem: ?=1 2 Proof (by mathematical induction): Base step: Show the theorem holds for n=1. 1 =1 1 + 1 2 Inductive step: Assume [or Suppose ] that __________________. WTS: ____________________. _____________________________________________ _____________________________________________ _____________________________________________ So the inductive step holds, completing the proof.
Proof by induction template ? =? ?+1 ? Theorem: ?=1 2 Proof (by mathematical induction): Base step: Show the theorem holds for n=1. 1 =1 1 + 1 For the inductive step, we want to prove that IF the theorem is true for some n >=[basis], THEN the theorem is true for n+1. How do we prove an implication p q? 2 Inductive step: Assume [or Suppose ] that __________________. WTS: ____________________. _____________________________________________ _____________________________________________ _____________________________________________ So the inductive step holds, completing the proof. A. Assume p, WTS q ( p and not q ). B. Assume p, WTS q. C. Assume q, WTS p. D. Assume p q, show it does not lead to contradiction.
Proof by induction template ? =? ?+1 ? Theorem: ?=1 2 Proof (by mathematical induction): Base step: Show the theorem holds for n=1. 1 =1 1 + 1 2 Inductive step: Assume [or Suppose ] that __________________. WTS: ____________________. _____________________________________________ _____________________________________________ _____________________________________________ So the inductive step holds, completing the proof. A.Assume n>=1 B.Assume that for all ? ?, ?=1 C.Assume that for some ? ?, ?=1 ? =? ?+1 ? =? ?+1 ? 2 ? 2
Proof by induction template ? =? ?+1 ? Theorem: ?=1 2 Proof (by mathematical induction): Base step: Show the theorem holds for n=1. 1 =1 1 + 1 2 Inductive step: Assume that for some ? 1, ?=1 WTS: ____________________. _____________________________________________ _____________________________________________ _____________________________________________ So the inductive step holds, completing the proof. ? =? ?+1 ? 2
Proof by induction template A.The negation is true. B.The theorem is true for some integer k+1. C.The theorem is true for n+1. D.The theorem is true for some integer n>=1 ? =? ?+1 ? Theorem: ?=1 2 Proof (by mathematical induction): Base step: Show the theorem holds for n=1. 1 =1 1 + 1 2 Inductive step: Assume that for some ? 1, ?=1 WTS: ____________________. _____________________________________________ _____________________________________________ _____________________________________________ So the inductive step holds, completing the proof. ? =? ?+1 ? 2
Proof by induction template ? =? ?+1 ? Theorem: ?=1 2 Proof (by mathematical induction): Base step: Show the theorem holds for n=1. 1 =1 1 + 1 2 Inductive step: Assume that for some ? 1, ?=1 WTS: The theorem is true for n+1: ?=1 _____________________________________________ _____________________________________________ _____________________________________________ So the inductive step holds, completing the proof. ? =? ?+1 ? 2 ?+1? =(?+1) ?+2 2
Proof by induction template ? =? ?+1 ? Theorem: ?=1 2 Proof (by mathematical induction): Base step: Show the theorem holds for n=1. 1 =1 1 + 1 2 Inductive step: ? =? ?+1 ? Assume that for some ? 1, ?=1 2 ?+1? =(?+1) ?+2 WTS: The theorem is true for n+1: ?=1 Next, we prove it, using any of the proof techniques that we learned (direct proof, proof by contradiction, etc) So the inductive step holds, completing the proof. 2
Proof of inductive step ? =? ?+1 ? Assume that for some ? 1, ?=1 2 ?+1? =(?+1) ?+2 WTS: The theorem is true for n+1: ?=1 ?+1 ? 2 ? = ? + (? + 1) (Isolation inductive case for n) ?=1 =? ? + 1 ?=1 (Using inductive assumption for n) + ? + 1 2 =? ? + 1 + 2(? + 1) (Simplification) 2 ? + 1 (? + 2) 2 =
Proof by induction template ? =? ?+1 ? Theorem: ?=1 2 Proof (by mathematical induction): Base step: Show the theorem holds for n=1. 1 =1 1 + 1 2 Inductive step: Assume that for some ? 1, ?=1 WTS: The theorem is true for n+1: ?=1 _____________________________________________ _____________________________________________ _____________________________________________ So the inductive step holds, completing the proof. ? =? ?+1 ? 2 ?+1? =(?+1) ?+2 2
Mathematical induction Want to prove For all integers n >= a, P(n). Base case: verify P(a) (usually by a simple direct calculation) Inductive step: Prove that ? ?,? ? ?(? + 1) P(a) P(a+1) P(a+2) P(a+3) P(a+4)
Mathematical induction Want to prove For all integers n >= a, P(n). Base case: verify P(a) (usually by a simple direct calculation) Inductive step: Prove that ? ?,? ? ?(? + 1) P(a) P(a+1) P(a+2) P(a+3) P(a+4)
Mathematical induction Want to prove For all integers n >= a, P(n). Base case: verify P(a) (usually by a simple direct calculation) Inductive step: Prove that ? ?,? ? ?(? + 1) P(a) P(a+1) P(a+2) P(a+3) P(a+4)
Another example: induction with sets Theorem: if |A|=n then |P(A)|=2n. Proof by induction on n. Base case: Inductive case: Assume WTS Proof
Another example: induction with sets Theorem: if |A|=n then |P(A)|=2n. Proof by induction on n. Base case: Inductive case: Assume WTS Proof A.Theorem is true for all n. B.Thereom is true for n=0. C.Theorem is true for n>0. D.Theorem is true for n=1.
Another example: induction with sets Theorem: if |A|=n then |P(A)|=2n. Proof by induction on n. Base case: n=0. So ? = ,? ? = { } and indeed |P(A)|=1=20 Inductive case: Assume WTS Proof
Another example: induction with sets Theorem: if |A|=n then |P(A)|=2n. Proof by induction on n. Base case: n=0. So ? = ,? ? = { } and indeed |P(A)|=1=20 Inductive case: Assume WTS Proof A.Theorem is true for some set B.Theorem is true for all sets C.Theorem is true for all sets of size n. D.Theorem is true for some set of size n.
Another example: induction with sets Theorem: if |A|=n then |P(A)|=2n. Proof by induction on n. Base case: n=0. So ? = ,? ? = { } and indeed |P(A)|=1=20 Inductive case: Assume theorem is true for n: for any set A of size n, |P(A)|=2n WTS Proof
Another example: induction with sets Theorem: if |A|=n then |P(A)|=2n. Proof by induction on n. Base case: n=0. So ? = ,? ? = { } and indeed |P(A)|=1=20 Inductive case: Assume theorem is true for n: for any set A of size n, |P(A)|=2n WTS Proof A.Theorem is true for some set of size >n. B.Thereom is true for all sets of size >n. C.Theorem is true for all sets of size n+1. D.Theorem is true for some set of size n+1.
Another example: induction with sets Theorem: if |A|=n then |P(A)|=2n. Proof by induction on n. Base case: n=0. So ? = ,? ? = { } and indeed |P(A)|=1=20 Inductive case: Assume theorem is true for n: for any set A of size n, |P(A)|=2n WTS: theorem is true for n+1: for any set B of size n+1, |P(B)|=2n+1 Proof
Another example: induction with sets Theorem: if |A|=n then |P(A)|=2n. Proof by induction on n. Base case: n=0. So ? = ,? ? = { } and indeed |P(A)|=1=20 Inductive case: Assume theorem is true for n: for any set A of size n, |P(A)|=2n WTS: theorem is true for n+1: for any set B of size n+1, |P(B)|=2n+1 Proof: try by yourself first
Proof of inductive step Assume: for any set A of size n, |P(A)|=2n WTS: for any set B of size n+1, |P(B)|=2n+1 Let B be any set of size n+1, ? = {?1,?2, ,??+1}. Define a set A by ? = {?1, ,??}. By the inductive assumption, as |A|=n we have |P(A)|=2n. We can partition ? ? = {?:? ?}, depending on whether C contains xn+1 or not: ?1= ?:? ?,??+1 ? = ? ? ?2= ?:? ?,??+1 ? We know that |S1|=2n. We will show that |S2|=2n. Since ? ? = ?1 ?2 and ?1 ?2= , this will show that ? ? = ?1+ ?2 = 2?+ 2?= 2?+1.
Proof of inductive step (contd) ?1= ?:? ?,??+1 ? = ? ? ?2= ?:? ?,??+1 ? Remaining to show: |?2| = 2?. Define a function ?:?1 ?2 by ? ? = ? {??+1}. It is one-to-one and onto Hence, ?1 = |?2|. We already know (by inductive assumption) that ?1 = 2?. Hence also ?2 = 2?.
Next class More fun with induction Read section 3.6 in Jenkyns, Stephenson
