1Inductive ReasoningGreat Theoretical Ideas In Computer ScienceVictor Adamchik CS 15-251 Spring 2010Lecture 2 Jan 14, 2010 Carnegie Mellon UniversityHomework must be TypesetYou may use any typesetting program you wish,TeX, LaTeX, Mathematica, …We Are Here to help!There are many office hours throughout the weekIf you have problems with the homework, don’t hesitate to ask for helpInductive ReasoningRaise your hand if you never heard of mathematical inductionAmerican BanksDomino Principle: Line up any number of dominos in a row; knock the first one over and they will all fall2Dominoes Numbered 1 to nDk “The kthdomino falls”If we set them up in a row then each one is set up to knock over the next:For all 1 ≤ k < n, Dk Dk+1D1 D2 D3 …All Dominoes FallPlain InductionSuppose we have some property P(k) that may or may not hold for a natural number n. To demonstrate that P(k) is true for all n is a little problematic.Inductive ProofsBase Case: Show that P(0) holdsInduction step: Assume that P(k) holds,show that P(k+1) also holdsIn the induction step, the assumption that P(k) holds is called the Induction HypothesisProof by Mathematical InductionIn formal notationP(0) , n P(n) P(n+1)Instead of attacking a problem directly, we only explain how to get a proof for P(n+1) out of a proof for P(n)TheoremThe sum of the first n odd numbers is n2Check on small values:1 = 11+3 = 41+3+5 = 91+3+5+7 = 16Induction HypothesisThe sum of the first n odd numbers is n21+3+5+...+(2n-1) = n23Induction step:Assume that P(n) holds, and show that P(n+1) also holdsAssume1+3+5+...+(2n-1) =n2Prove1+3+5+...+(2n+1) =(n+1)21 + 3 + 5 + … + (2n-1) = n21 + 3 + 5 +… + (2n-1) + (2n+1) = n2 + (2n+1)1 + 3 + 5 +… + (2n+1) = (n+1)2Soundness of InductionHow do we know that this really works?Soundness of InductionProof by contradiction. Assume that for some assertion P(n), we can establish the base case, and the induction step, but nonetheless it is not true that P(n) holds for all n. So, for some values of n, P(n) is false. Soundness of InductionLet n0 be the least such n.Certainly, n0cannot be 0.Thus, it must be n0= n1+1, where n1< n0. Soundness of InductionNow, by our choice of n0, this means that P(n1) holds.4Soundness of InductionNow, by our choice of n0, this means that P(n1) holds. because n1< n0Soundness of InductionBut then by Induction Hypothesis,P(n1+1) also holds. Soundness of InductionBut then by Induction Hypothesis, P(n1+1) also holds. But that is the same as P(n0), and we have a contradiction.Review that proofwe can pick n0 to be the least n where P(n) fails.Least Element PrincipleEvery non-empty subset of the natural numbers must contain a least element.5Some CommentsWe have chosen to describe the induction step as moving from n to n+1, where n >= 0. There is the obvious alternative to change the induction step from n-1 to n, where n > 0.Some CommentsThere is nothing sacred about the base case n=0, we could just as well start at n = 11.ATM MachineSuppose an ATM machine has only two dollar and five dollar bills. You can type in the amount you want, and it will figure out how to divide things up into the proper number of two's and five's.Claim: The ATM can generate any output amount n >= 4.ProofBase case: n = 4. 2 two's, done.Induction step: suppose the machine can already handle n>=4 dollars. How do we proceed for n+1 dollars?ProofCase 1: The n dollar output contains a five. Then we can replace the five by 3 two's to get n+1 dollars.ProofCase 2: The n dollar output contains only two's. Since n>=4, there must be at least 2 two's. Remove 2, and replace them by 1 five. Done.6TheoremEvery natural number > 1 can be factored into primesBase case:2 is prime P(2) is trueInductive hypothesis:P(n) can be factored into primesThis shows a technical point about mathe-matical inductionTheorem?Every natural number > 1 can be factored into primesA different approach:Assume 2,3,…,n-1 all can be factored into primesThen show that n can be factored into primesStrong InductionEstablish Base Case: P(0)Establish Domino Effect:Assume j<n, P(j) use that to derive P(n)TheoremEvery natural number n > 1 can be factored into primesBase case:2 is prime P(2) is trueInductive hypothesis:P(j), j<n can be factored into primesCase 1: n is primeCase 2: n is composite, n = p qFaulty InductionClaim. 6 n=0 for all n>=0.Base step: Clearly 6*0 = 0.Induction step: Assume that 6 k=0 for all 0<=k<=n.We need to show that 6 (n+1) is 0.Write n+1=a+b., where a,b>0. 6 (n+1) = 6(a+b) = 6 a + 6 b = 0 + 0 = 07And there are more ways to do inductive proofs Invariant (n): 1. Not varying; constant. 2. Mathematics.Unaffected by a designated operation, as a transformation of coordinates.Yet another way of packaging inductive reasoning is to define “invariants”Invariant (n): 3. Programming.A rule, such as the ordering of an ordered list, that applies throughout the life of a data structure or procedure. Each change to the data structure maintains the correctness of the invariantOdd/Even Handshaking Theorem At any party at any point in time define a person’s parity as ODD/EVEN according to the number of hands they have shakenStatement: The number of people of odd parity must be evenIf 2 people of the same parity shake, they both change and hence the odd parity count changes by 2 – and remains evenStatement: The number of people of odd parity must be evenInitial case: Zero hands have been shaken at the start of a party, so zero people have odd parityInvariant Argument:If 2 people of different parities shake, then they both swap parities and the odd parity count is unchangedInductive reasoning is the high level idea“Standard” Induction“Strong” Induction “Least Element Principal”“Invariants”all just different packaging8Induction is also how we can define and construct our worldSo many things, from buildings to computers, are built up stage by stage, module by module, each depending on the previous stagesInductive DefinitionA binary tree is either empty tree or a node containing left and right binary trees. A linked list is either empty list or a node followed by a linked listF(1) = 1 recursive functionF(n) = F(n/2) + 1P(n) = 2 + P(n-1)P(2) = 1Pancakes With A Problem!Bring-to-top MethodFractalsFractals are geometric objects that are self-similar, i.e. composed of infinitely many pieces, all of which look the same.The Koch GameProductions Rules:Alphabet: { F, +, - }Start word:
View Full Document