Mastering Strong Induction for Discrete Math Studies
Delve into the power and techniques of strong induction in the context of discrete mathematics through examples and detailed explanations presented by Professor Shachar Lovett. Learn to prove mathematical statements using both strong and regular induction methods, with practical applications in divisibility and coin problems.
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
Clicker frequency: CA CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/
Todays topics Strong induction Section 3.6.1 in Jenkyns, Stephenson
Strong vs regular induction Goal is the same: prove ? 1,?(?) Standard induction: Base case: n=1 From one step to the next: ? 1,? ? ?(? + 1) Strong induction: Base case: n=1 Assume more in each step: ? 1, ? 1 ? ? ?(? + 1)
Strong vs regular induction Goal is the same: prove ? 1,?(?) Standard induction: Base case: n=1 From one step to the next: ? 1,? ? ?(? + 1) P(1) P(2) P(3) P(n) P(n+1) Strong induction: Base case: n=1 Assume more in each step: ? 1, ? 1 ? ? ?(? + 1) P(1) P(2) P(3) P(n) P(n+1)
5 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 cases: 8=3+5, 9=3+3+3, 10=5+5 Assume it holds for all prices 8...p-1, prove for price p when ? 11 Proof: since ? 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!
Another example: divisibility Thm: For all integers n>1, n is divisible by a prime number. Before proving it (using strong induction), lets first review some of the basic definitions, but now make them precise
Definitions and properties for this proof Definitions: n is prime if ?,? ?,? = ?? (? = 1 ? = 1) n is composite if n=ab for some 1<a,b<n 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).
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
Thm: For all integers n>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.
Thm: For all integers n>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.
Thm: For all integers n>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.
Thm: For all integers n>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 ? ? ? WTS that A. n+1 is divisible by a prime number. B. k+1 is divisible by a prime number. C. Other/none/more than one So the inductive step holds, completing the proof.
13 Thm: For all integers n>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.
Theorems about recursive definitions Consider the following sequence: d1=9/10 d2=10/11 dn=dn-1 * dn-2 ? 3 Theorem: ? 1,0 < ??< 1 Facts the we will need for the proof: If 0<x,y<1 then 0<xy<1 Algebra, etc
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.
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.
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>0, 0<dn<1. B. For some int n>1, 0<dk<1, for all integers k where 1 k n. C. Other/none/more than one WTS that So the inductive step holds, completing the proof.
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>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 WTS that So the inductive step holds, completing the proof.
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 the theorem holds for n 2. 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.
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?
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? YES! ? ? 1 1 + 5 2 1 1 5 2 ??= 5 5
22 Fibonacci numbers Rule: F1=1, F2=1, Fn=Fn-2+Fn-1. We will prove an upper bound: ? =1 + 5 ?? ??, 2 Proof by strong induction.
23 Fibonacci numbers Rule: F1=1, F2=1, Fn=Fn-2+Fn-1. We will prove an upper bound: ? =1 + 5 ?? ??, 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
24 Fibonacci numbers Rule: F1=1, F2=1, Fn=Fn-2+Fn-1. We will prove an upper bound: ? =1 + 5 ?? ??, 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
25 Fibonacci numbers Rule: F1=1, F2=1, Fn=Fn-2+Fn-1. We will prove an upper bound: ? =1 + 5 ?? ??, 2 Proof by strong induction. Base case: n=1,2 Verify by direct calculation: ?1= 1 ?,?2= 1 ?2
26 Fibonacci numbers Rule: F1=1, F2=1, Fn=Fn-2+Fn-1. We will prove an upper bound: ? =1 + 5 ?? ??, 2 Proof by strong induction. Base case: n=1,2 A. Fn=Fn-1+Fn-2 B. Fn Fn-1+Fn-2 C. Fn=rn D. Fn rn E. Other Inductive case: show
Proof of inductive case WTS: ?? ?? What can we use? Definition: ??= ?? 1+ ?? 2 Inductive assumption: ?? ?? ? < ? So, we know that ?? ?? 1+ ?? 2 Need to show that ?? 1+ ?? 2 ??
Proof of inductive case (contd) Need to show that ?? 1+ ?? 2 ?? Equivalently: r + 1 ?2 It turns out that this is satisfied by our choice of ? =1+ 5 2 In fact, it is a root of the quadratic ?2 ? 1 = 0 (so in fact r + 1 = ?2) The other root is 1 5 2; recall the formula 1 1 + 5 2 ? ? 1 1 5 2 ??= 5 5
29 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
Next class Applying proof techniques to analyze algorithms Read section 3.7 in Jenkyns, Stephenson
