Algorithms and Abstract Data Types
Algorithms and Abstract Data Types CMPS 101
Popular in Course
Popular in ComputerScienence
This 5 page Class Notes was uploaded by Dr. Elyssa Ratke on Monday September 7, 2015. The Class Notes belongs to CMPS 101 at University of California - Santa Cruz taught by Staff in Fall. Since its upload, it has received 53 views. For similar materials see /class/182263/cmps-101-university-of-california-santa-cruz in ComputerScienence at University of California - Santa Cruz.
Reviews for Algorithms and Abstract Data Types
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/07/15
CISlUl Handout 6 David Helmhold October 8 1998 Induction Proofs 1 Introduction to Induction This handout describes why an induction proof works provides the correct layout for a proof by induction and gives several examples of correct inductions In addition Section 3 gives several common errors in induction proofs and describes why they are wrong To understand why induction works it may be useful to consider the difference between a straightline program and a recursive program For example a straightline program to compute 5 might work follows 2 3 4 5 while a recursive program might look more like int factoria1int n int total if 1 then total 1 returntota1 else total factoria1n1 n returntota1 where 5 is computed by calling factoria15 Although the recursive program is actually longer for 71 5 you can easily see that it saves a lot of writing when 71 100 000 or even when 71 50 Note that both the straightline program and the recursive program make exactly the same assignments to total the recursive program is just a of describing these assignments more generally In fact we can describe the recursive algorithm pictorially follows Induction works in almost the same way Many proofs can be viewed as straight line proofs where the chain of reasoning starts with a fact and proceeds using other facts to reach the desired conclusion However just like a single straightline program cannot compute different factorials proving a statement like for all positive integers or for all integers greater than k can be very difficult when only a straightline proof is allowed Just like the recursive factorial program represents a collection of different straight line programs one for each positive value of n an inductive proof represents an in nite number of straightline proofs one for each suitable value of n Thus one is allowed to use a correct inductive proof to conclude that that the desired property holds for all suitable values of n In the factorial programs we moved from one value of n to the next by multiplying factorial nl by n In inductive proofs the connection between the different values of n can be much more subtle Therefore the key to any inductive proof is the various inductive hypotheses the things that get done for each value of n Just like n has a different value for different n we use a different inductive hypothesis for each value of n I use I H n to denote the particular inductive hypothesis for the value n In fact each H is a statement that could be either true or false such as All complete binary trees of height n have 2 1 1 nodes or If a binary tree has n degree2 nodes then it has n 1 leaves or for all n the 217 2 nn 12 In this class we do induction over structures like graphs and trees This is related to induction over the integers in the summation example above but requires a size measure on the structures Basically you stratify the set of all structures into subsets based on the size of the structures Typical size measures are number of nodes or height for trees and number of nodes or edges for graphs Usually the de nition of the kind of structure gives a hint to what to use the size measure large structures often incorporate smaller structures The inductive proof includes a base case to prove that for some concrete value k usually 16 U or k 1 the statement 111k is true It is certainly permissible and sometimes necessary to include several base cases proofs of 1H for several different values of k We will see an example of this in Section 2 A base case is like the total 1 assignments in the factorial problem they establish the needed fact to base the induction on a rm foundatation The recursive part of the factorial program is like the inductive step Just like the recursive part generates many assignments to total the inductive step generates many subproofs Just like the assignments to total are spliced together to compute whatever n we want from the total 1 assignment the inductive step allows us to splice together a proof of I H 71 from the base cases for whatever large value of 71 we want Although the inductive proof contains explicit proofs of I H 71 only when 71 is one of the base cases it can be viewed as a template for generating proofs of 1117 for whatever nvalues are desired That is why inductive proofs allow us to conclude that IH71 is true for all large values of n ou don t need to write down all these proofs just enough so that anyone with enough paper can write down whichever I H 71 proof they need Important note Both the inductive step and the base cases are proofs and must adhere to the proof rules Although each of these should start the with a description of what is to be shown the proof part must start with a fact and continue with facts until the desired conclusion is reached Each fact should be easily justi ed and veri ed either by referencing a previously established fact a stated assumption a wellknown theorem or simple algebra If you want to use a complicated fact that doesn t t into one of these categories call the fact a claim write a separate proof of the claim and then continue with your induction 2 Examples of Induction Proof H The rst example is the nal problem in the midterm For this problem you need only one base case Recall from the midterm that an extended binary tree contains just a single external node or is an internal node the root connected to two disjoint subtrees which are themselves extended binary trees Note the recursion in the de nition this should be exploited in your proof well Also the number of internal nodes is a natural size measure for extended binary trees The total number of nodes can be used well Finally the proof exploits the following fact the set of nodes in any tree is the root if plus the union of the nodes in the subtrees Thus we can count nodes by counting up the nodes in the subtrees and adding in the root M Theorem In any extended binary tree the number of external nodes is one greater than the number of internal nodes Proof By induction on number of internal nodes 1Hk All extended binary trees with k internal nodes have 16 1 external nodes Base Case Show 1H Extended binary trees with zero internal nodes are just a single external node so the number of internal nodes is one less than number of external nodes in this case Inductive Step Assume J gt 0 and 111k holds for 0 3 k lt J we need to show IHJ also holds here Let T be an arbitrary extended binary tree with J internal nodes Since J gt 0 T s root is an internal node connected to two extended binary tree T and Tr Since the root is in neither sub treeand all nodes in the subtrees are in T T and T each has less than J internal nodes Let 7 and 71 be the number of internal nodes in T and Tr Using 1117 and IH71 T and T have 71 1 and 71 1 external nodes respectively The root is an internal node so T has J 71 71 1 internal nodes similarly adding up the external nodes in the subtrees we get that T has 71 72 2 J 1 external nodes Therefore arbitrary trees with j internal nodes have one more external node than internal nodes and IHJ is shown QED The second example is about Fibonacci number The de nition is follows F0 0 F1 1 F F1 F2 for 39139 Z 2 The general form is F 031 where 05 1 52 1 This induction will require two base cases Theorem The ith Fibonacci number satis es F 031 Proof By induction on integer number 71 Z 0 IHUC The theorem holds for k 2 0 ie Fk Base Case Show IH0 and IH1 For 1110 F0 0010 yaw S 1 1S 0 1110 holds here For 1111 1711 gal 11 11F5 1 32 1 525 1 1111 holds here Inductive StepAssume 71 gt 1 and 1Hk holds for 0 g k lt 71 we need to show 100 also holds here By the de nition of Fibonacci number F Fn1 Fn2 Since both 71 1 and 71 2 less than 71 and at least 0 we can use IH71 1 and IH71 2 37171 wail F 7 xS xS 1 5 7quot lit5 quot 1 H lt 2 gt lt 2 gt lt gt 5 37172 7172 1 H M n72 n72 lt gt Han 1 75 lt1 5 n72 2 n72 2 lt gt lt gt 4 lt gt 5 Therefore IH71 holds QED Common Errors in Induction Proof Base Case For induction proof you must prove the base case because this is the foundation of the induction proof Without a base case the following proof has no meaning One common error is to forget to prove the base case Another one is proving an insufficient number of base cases Although one base case is usually enough many problems like the Fibonacci number example F 1 Fniz require two base case values in order to use the recurrence equation Eg if you only prove the base case for i 0 you might wind up using F1 F0 171 in the inductive step but this is not part of the de nition of the Fibbonacci sequence Similarly if you have proven the base case only for i 1 then you can use F2 F1 F0 but you have not shown that F0 meets the required form Premise Whenever to prove the theorem don t forget the premise of the theorem The following is an example that uses the induction to get a wrong conclusion Theorem If 71 is an even number and 71 gt 2 then 71 is a power of two Proof By induction on the even number n 1Hk If k is an even number and k gt 2 then k 21 where 39i is a natural number Base Case Since 4 is the smallest even number larger than 2 we need to show IH4 4 22 IH4 holds here Inductive Step Assume 71 is a even number and 71 gt 2 IHk holds for any even number k and k lt 71 we need to show 100 holds here Since 71 is a even number so 71 2k where k lt 71 Using the hypothesis we can write k 21 so 2k 2 X 21 2139 and 100 holds QED
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'