Inductive Proofs Must Have Base Case value where you prove it is true about the base case Inductive Hypothesis value where you state what will be assume in this proof Inductive Step value show where you state what will be proven below proof where you prove what is stated in the show portion this proof must use the Inductive Hypothesis sometime during the proof n Prove this statement i 1 Base Case n 1 1 i 1 i n n 1 2 n n 1 1 1 1 2 1 2 2 2 i 1 Inductive Hypothesis n p p i 1 i p p 1 2 Inductive Step n p 1 p 1 Show p 1 p 1 1 i 2 i 1 Proof in class 1 Variations 2 4 6 8 20 If you can use the fact n i 1 i n n 1 2 Rearrange it into a form that works If you can t you must prove it from scratch Less Mathematical Example If all we had was 2 and 5 cent coins we could make any value greater than 3 Base Case n 4 Inductive Hypothesis n k Inductive Step n k 1 show proof 2 More Examples to be done in class n Z 1 3 n 3 n n n Z 0 2 k 2 n 1 1 k 0 Geometric Progression n 1 ar a j 1 0 r R a R n Z ar r 1 j 0 n Proving Inequalities with Induction Inductive Hypothesis has the form y z Inductive Step needs to prove something of the form x z Two methods for the proof part use whichever you like transitivity find a value between b prove that b z prove that x b book method Substitute unequals as long as the signs don t change or Add unequals to unequals as long as always adding correct sides 3 Prove this statement n Z 3 2 n 1 2 n Base Case n 3 LHS 2 3 1 6 1 7 LHS RHS RHS 23 8 Inductive Hypothesis n k k 2k 1 2 Inductive Step n k 1 Show 2 k 1 1 2 k 1 Proof both methods done in class Another Example with inequalities n Z 2 x Z 1 1 nx 1 x n 4 Strong Induction Implication changes slightly if true for all lesser elements then true for current P i i Z a i k P k P i i Z a i k P k 1 Regular Induction P k P k 1 P k 1 P k Recurrence Relation Example Assume the following definition of a function a0 1 a1 1 a2 3 k Z 3 ak ak 1 ak 2 ak 3 Prove the following definition property n Z 0 an Z odd 5 All Integers greater than 1 are divisible by a prime Base Case n 2 2 2 2 Zprime Inductive Hypothesis n i i 2 i k p Zprime p i Inductive Step n k show p Zprime p k proof A Factorial Example n Z 2 n 4 2n n 1 n 2 6 Another Example Assume the following definition of a recurrence relation a1 0 a2 2 i Z 3 ai 3a i 2 2 Prove that all elements in this relation have this property n Z 1 an Z even Well Ordering Principle For any set S of one or more integers all larger than some value S has a least element 7 Use this to prove the Quotient Remainder Theorem The quotient remainder theorem said Given any positive integer n and any positive integer d There exists an r and a q where n dq r where 0 r d which are integers which are unique Steps to proving the quotient remainder theorem Define S as the set of all non negative integers in the form n dk all integers k Prove that it is non empty Prove that we can apply the Well Ordering Principle Then it has a least element Prove that the least element r is 0 r d 8
View Full Document
Unlocking...