Peer Instruction in Discrete Mathematics: Induction Algorithms
The concept of mathematical induction and algorithmic proofs in discrete mathematics through examples and visual explanations. Learn how to apply strong induction to solve problems involving divisibility and recursion sequences. Discover an algorithm for paying prices using 3-cent and 5-cent coins, with a step-by-step breakdown of the process.
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
Creative Commons License CSE 20 Discrete Mathematics Dr. Cynthia Bailey Lee Dr. Shachar Lovett Peer Instruction in Discrete Mathematics by Cynthia Leeis licensed under a Creative Commons Attribution- NonCommercial-ShareAlike 4.0 International License. Based on a work at http://peerinstruction4cs.org. Permissions beyond the scope of this license may be available at http://peerinstruction4cs.org.
2 Today s Topics: 1. Quick wrap-up of Monday s coin example 2. Strong vs regular induction 3. Strong induction examples: Divisibility by a prime Recursion sequence: product of fractions
3 Thm: For all prices p >= 8 cents, the price p can be paid using only 5-cent and 3-cent coins. Proof (by mathematical induction): Basis step: Show the theorem holds for p=8 (by example, e.g. p=3+5) Inductive step: Assume [or Suppose ] that the theorem holds for some p 8. WTS that the theorem holds for p+1. p 8. Assume that p=5n+3m where n,m 0 are integers. We need to show that p+1=5a+3b for integers a,b 0. Partition to cases: Case I: n 1. In this case, p+1=5*(n-1)+3*(m+2). Case II: m 3. In this case, p+1=5*(n+2)+3*(m-3). Case III: n=0 and m 2. Then p=5n+3m 6 which is a contradiction to p 8. So the inductive step holds, completing the proof.
4 We created an algorithm! Our proof actually allows us to algorithmically find a way to pay p using 3-cent and 5-cent coins Algorithm for price p: start with 8=3+5 For x=8...p, in each step adjust the number of coins according to the modification rules we ve constructed to maintain price x
5 Algorithm pseudo-code PayWithThreeCentsAndFiveCents: Input: price p 8. Output: integers n,m 0 so that p=5n+3m Let x=8, n=1, m=1 (so that x=5n+3m). While x<p: a) x:=x+1 b) If n 1, set n:=n-1, m:=m+2 c) Otherwise, set n:=n+2, m:=m-3 Return (n,m) 1. 2. 3.
6 Algorithm pseudo-code PayWithThreeCentsAndFiveCents: Input: price p 8. Output: integers n,m 0 so that p=5n+3m Let x=8, n=1, m=1 (so that x=5n+3m). 1. While x<p: a) x:=x+1 b) If n 1, set n:=n-1, m:=m+2 c) Otherwise, set n:=n+2, m:=m-3 2. Invariant: x=5n+3m Invariant: x=5n+3m Return (n,m) We proved that n,m 0 in this process always; this is not immediate from the algorithm code 3.
7 Algorithm run example x=8: n=1, m=1 While x<p: a) b) c) 8= Invariant: x=5n+3m x:=x+1 If n 1, set n:=n-1, m:=m+2 Otherwise, set n:=n+2, m:=m-3 9= 10 = 11= 12 =
8 Algorithm properties Theorem: Algorithm uses at most two nickels (i.e n 2) Proof: by induction on p Try to prove it yourself first! x=8: n=1, m=1 While x<p: a) b) c) Invariant: x=5n+3m x:=x+1 If n 1, set n:=n-1, m:=m+2 Otherwise, set n:=n+2, m:=m-3
9 x=8: n=1, m=1 While x<p: a) b) c) Invariant: x=5n+3m x:=x+1 If n 1, set n:=n-1, m:=m+2 Otherwise, set n:=n+2, m:=m-3 Algorithm properties Theorem: Algorithm uses at most two nickels (i.e n 2). Proof: by induction on p Base case: p=8. Algorithm outputs n=m=1. Inductive hypothesis: p=5n+3m where n 2. WTS p+1=5a+3b where a 2. Proof by cases: Case I: n 1. So p+1=5(n-1)+3(m+2) and a=n-1 2. Case II: n=0. So p+1=5*2+3(m-3). a=2. In both cases p+1=5a+3b where a 2. QED
10 2. Strong induction examples DIVISIBILITY BY A PRIME
11 Strong vs regular induction Prove: n 1 P(n) Base case: P(1) Regular induction: P(n) P(n+1) P(1) P(2) P(3) P(n) P(n+1) Strong induction: (P(1) P(n)) P(n+1) Can use more assumptions to prove P(n+1) P(1) P(2) P(3) P(n) P(n+1)
12 Example for the power of strong induction Theorem: For all prices p >= 8 cents, the price p can be paid using only 5-cent and 3-cent coins Proof: Base case: 8=3+5, 9=3+3+3, 10=5+5 Assume it holds for all prices 1..p-1, prove for price p when p 11 Proof: since p-3 8 we can use the inductive hypothesis for p-3. To get price p simply add another 3-cent coin. Much easier than standard induction!
13 3. Strong induction examples DIVISIBILITY BY A PRIME
14 Definitions and properties for this proof Definitions: n is prime if n is composite if n=ab for some 1<a,b<n = = = , : 1 1 a b n ab a b Prime or Composite exclusivity: All integers greater than 1 are either prime or composite (exclusive or can t be both). Definition of divisible: n is divisible by d iff n = dk for some integer k. 2 is prime (you may assume this; it also follows from the definition).
15 Definitions and properties for this proof (cont.) Goes without saying at this point: The set of Integers is closed under addition and multiplication Use algebra as needed
16 Thm: For all integers n greater than 1, n is divisible by a prime number. Proof (by strong mathematical induction): Basis step: Show the theorem holds for n = ________. Inductive step: Assume [or Suppose ] that WTS that So the inductive step holds, completing the proof.
17 Thm: For all integers n greater than 1, n is divisible by a prime number. Proof (by strong mathematical induction): Basis step: Show the theorem holds for n = ________. Inductive step: Assume [or Suppose ] that A. 0 B. 1 C. 2 D. 3 E. Other/none/more than one WTS that So the inductive step holds, completing the proof.
18 Thm: For all integers n greater than 1, n is divisible by a prime number. Proof (by strong mathematical induction): Basis step: Show the theorem holds for n = 2. Inductive step: Assume [or Suppose ] that A. For some integer n>1, n is divisible by a prime number. B. For some integer n>1, k is divisible by a prime number, for all integers k where 2 k n. C. Other/none/more than one WTS that So the inductive step holds, completing the proof.
19 Thm: For all integers n greater than 1, n is divisible by a prime number. Proof (by strong mathematical induction): Basis step: Show the theorem holds for n = 2. Inductive step: Assume [or Suppose ] that For some integer n>1, k is divisible by a prime number, for all integers k where 2 k n. A. n+1 is divisible by a prime WTS that number. B. k+1 is divisible by a prime number. C. Other/none/more than one So the inductive step holds, completing the proof.
20 Thm: For all integers n greater than 1, n is divisible by a prime number. Proof (by strong mathematical induction): Basis step: Show the theorem holds for n=2. Inductive step: Assume that for some n 2, all integers 2 k n are divisible by a prime. WTS that n+1 is divisible by a prime. Proof by cases: Case 1: n+1 is prime. n+1 divides itself so we are done. Case 2: n+1 is composite. Then n+1=ab with 1<a,b<n+1. By the induction hypothesis, since a n there exists a prime p which divides a. So p|a and a|n+1. We ve already seen that this implies that p|n+1 (in exam give full details!) So the inductive step holds, completing the proof.
21 2. Strong induction examples RECURSION SEQUENCE: PRODUCT OF FRACTIONS
22 Definitions and properties for this proof Product less than one: Algebra, etc., as usual
23 Definition of the sequence: d1 = 9/10 d2 = 10/11 dk = (dk-1)(dk-2) for all integers k 3 Thm: For all integers n>0, 0<dn<1. Proof (by strong mathematical induction): Basis step: Show the theorem holds for n = ________. Inductive step: Assume [or Suppose ] that WTS that So the inductive step holds, completing the proof.
24 Definition of the sequence: d1 = 9/10 d2 = 10/11 dk = (dk-1)(dk-2) for all integers k 3 Thm: For all integers n>0, 0<dn<1. Proof (by strong mathematical induction): Basis step: Show the theorem holds for n = ________. Inductive step: Assume [or Suppose ] that A. 0 B. 1 C. 2 D. 3 E. Other/none/more than one WTS that So the inductive step holds, completing the proof.
25 Definition of the sequence: d1 = 9/10 d2 = 10/11 dk = (dk-1)(dk-2) for all integers k 3 Thm: For all integers n>0, 0<dn<1. Proof (by strong mathematical induction): Basis step: Show the theorem holds for n = 1,2. Inductive step: Assume [or Suppose ] that A. For some int n>2, 0<dn<1. B. For some int n>2, 0<dk<1, for all integers k where 3 k n. C. Other/none/more than one WTS that So the inductive step holds, completing the proof.
26 Definition of the sequence: d1 = 9/10 d2 = 10/11 dk = (dk-1)(dk-2) for all integers k 3 Thm: For all integers n>0, 0<dn<1. Proof (by strong mathematical induction): Basis step: Show the theorem holds for n = ________. Inductive step: Assume [or Suppose ] that theorem holds for n 2 WTS that A. For some int n>0, 0<dn<1. B. For some int n>1, 0<dk<1, for all integers k where 1 k n. C. 0<dn+1<1 D. Other/none/more than one So the inductive step holds, completing the proof.
27 Definition of the sequence: d1 = 9/10 d2 = 10/11 dk = (dk-1)(dk-2) for all integers k 3 Thm: For all integers n>0, 0<dn<1. Proof (by strong mathematical induction): Basis step: Show the theorem holds for n=1,2. Inductive step: Assume [or Suppose ] that for some int n 3, the theorem holds for all int k, n k 3. (i.e. 0<dk<1 for all k between 3 and n, inclusive) WTS that 0<dn+1<1. By definition, dn+1=dn dn-1. By the inductive hypothesis, 0<dn-1<1 and 0<dn<1. Hence, 0<dn+1<1. So the inductive step holds, completing the proof.
28 3. Fibonacci numbers Verifying a solution
29 Fibonacci numbers 1,1,2,3,5,8,13,21, Rule: F1=1, F2=1, Fn=Fn-2+Fn-1. Question: can we derive an expression for the n-th term? n n + 1 1 5 1 1 5 YES! = n F 2 2 5 5
30 Fibonacci numbers Rule: F1=1, F2=1, Fn=Fn-2+Fn-1. We will prove an upper bound: + 1 5 = n , n F r r 2 Proof by strong induction. Base case: A. n=1 B. n=2 C. n=1 and n=2 D. n=1 and n=2 and n=3 E. Other
31 Fibonacci numbers Rule: F1=1, F2=1, Fn=Fn-2+Fn-1. We will prove an upper bound: + 1 5 = n , n F r r 2 Proof by strong induction. Base case: n=1, n=2. Verify by direct calculation = = 2 1 F r 1 F r 1 2
32 Fibonacci numbers Rule: F1=1, F2=1, Fn=Fn-2+Fn-1. + 1 5 Theorem: = n , n F r r 2 Base cases: n=1,n=2 A. Fn=Fn-1+Fn-2 B. Fn Fn-1+Fn-2 C. Fn=rn D. Fn rn E. Other Inductive step: show
33 Fibonacci numbers = + n Inductive step: need to show , 1 5 , n F r r 2 What can we use? Definition of Fn: Inductive hypothesis: = + F F F 2 1 n n n 1 2 n n , F r F r 1 2 n n That is, we need to show that r + 2 1 n n n r r
34 Fibonacci numbers Finishing the inductive step. Need to show: + 2 1 n n n r r r 1 r + 2 r Simplifying, need to show: = 1 r + = + 2 Choice of actually satisfied (this is why we chose it!) 1 5 r r 2 QED
35 Fibonacci numbers - recap Recursive definition of a sequence Base case: verify for n=1, n-2 Inductive step: Formulated what needed to be shown as an algebraic inequality, using the definition of Fn and the inductive hypothesis Simplified algebraic inequality Proved the simplified version
