Explore the concept of mathematical induction through various examples and a detailed framework for writing proofs. Understand the principles of strong and weak induction, as well as applying induction to recurrence relations. Learn the step-by-step process of proving statements for different values using induction.
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.
Induction Most general view: Let ?(?) be a statement which is a function of ? e.g. ?(?) could be "1 + 2 + 4 + 2? 1= 2? 1" We wish to prove ?(?) is true for all ? in some category e.g. For the above ?(?), we d want to show it holds for all positive integers We ll start by showing ?(?) is true for some basic ? (e.g. 1), and then build upon that to show ?(?) holds for larger values.
Induction framework When writing a proof by induction, the steps generally go as follows: 1. Give the statement you re trying to prove and the set of values you want to prove it s true for. 2. Determine the base case value for the statement you want to prove, and show the statement holds for the base case value. 3. Show that if the statement holds for one value or set of values (the inductive hypothesis), it holds for another value. 4. From steps 2 and 3, conclude it s true for all the desired values.
Strong vs Weak Induction In the previous examples, the inductive hypothesis was to assume that the statement held for just one value (i.e. if ? is the statement we wish to prove, we would show ?(? + 1) assuming ?(?) is true). This is known as simple or weak induction. Sometimes, it s easier to assume it holds for multiple values. For example, we might try to prove ? ? + 1 by assuming ?(?) and ? ? 1 are true, or by assuming all of ? 1 ,? 2 ?(?) are true. This is known as strong induction. The two use the same framework outlined previously, the only difference is the inductive hypothesis used.
Induction Example Show that if ?0= 1,?1= 1,??= ?? 2+ ?? 1(this is the Fibonacci sequence) that ?? 2?.
Induction on Recurrence Relations The most formal way to prove a recurrence relation holds is proof by induction. In using induction to prove ? ? ? ? ? , the statement we are trying to prove is "?(?) ? ?(?)" for all sufficiently large integer values of ? and some constant ? of our choice (it can be arbitrarily large as long as it s constant). Then, the outline for such a proof is as follows: 1. Argue that ? 1 (or ? ? for some constant ?) is less than ? ?(1) since ? can be arbitrarily large. 2. Show that if ? ? ? ?(?) for ? = 1,2, ? then ? ? + 1 ? ?(? + 1) 3. Conclude that ? ? ? ?(?) for all positive integer values of ?.
Induction on Recurrence Relations Example Example: Show ? ? = ? ? 1 + ?,? 1 = 1 satisfies ? ? ?(?2) We claim ? 1 ? if we pick a sufficiently large ?. Then, assume ? ? ??2for ? = 1,2, ?. We wish to show ? ? + 1 ? ? + 12 ? ? + 1 = ? ? + ? + 1 ??2+ ? + 1 ??2+ 2?? + ? ?? ? 1 ? ? + 12 Thus for all ? 1, ? ? ??2so ? ? ? ?2
Big-Oh Problems Recall that ? ? ? ? ? ? ? ? ?(?) for ? ?0. Show that 1. If ?1? ? ?2? ? max ?2? ,?2? 2. If ?1? ? ?2? ? ?2? ?2(?) means there exists some ?0,? such that and ?1? ? ?2? , then ?1? + ?1? and ?1? ? ?2? , then ?1? ?1(?)
Big-Oh Problems Order the following terms from least to greatest (i.e. if ?(?) comes before ?(?) in your order, then it should be true that ? ? ? ? ? ) ?log?,1.1?,log2?,?! ,1 ?,log?2,?2
