1Inductive 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 proofProve this statement:Base Case (n=1):Inductive Hypothesis (n=p):Inductive Step (n=p+1):Show: Proof:(in class)=+=ninni12)1(==111ii1222)11(12)1(==+=+nn=+=pippi12)1(+=+++=112)1)1)((1(pippi2Variations• 2+4+6+8+…+20 = ??• If you can use the fact:• Rearrange it into a form that works.• If you can’t – you must prove it from scratch=+=ninni12)1(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:3More Examples to be done in class••• Geometric Progression)(|3,31nnZn −∈∀≥122100−=∈∀+=≥nnkkZn1,1001−−=∈∀∈∀∈∀+=≥>raararZnRaRrnnjjProving 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 changeor• Add unequals to unequals as long as always adding correct sides4Prove this statement:Base Case (n=3):Inductive Hypothesis (n=k):Inductive Step (n=k+1):Show: Proof:(both methods done in class)7161)3(2:=+=+LHS82:3=RHSkk212≤+121)1(2+≤++kkRHSLHS≤nnZn 212,3≤+∈∀≥Another Examplewith inequalitiesnxnxZxZn )1(1,12+≤+∈∀∈∀−>≥5Strong Induction• Implication changes slightly– if true for all lesser elements, then true for current• P(i) ∀i∈Z ai<k → P(k)• P(i) ∀i∈Z ai 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:• Prove the following definition property:11=a 32=a3213,−−−≥−+=∈∀kkkkaaaaZkoddnZaZn ∈∈∀≥,010=a6All Integers greater than 1are divisible by a primeBase Case (n=2):2|2 2 ∈ZprimeInductive Hypothesis (n=i ∀i 2≤i<k):∃p ∈Zprimep|iInductive Step (n=k):show: ∃p ∈Zprimep|kproof:A Factorial Example22)!()!2(14,nnnZnn<+∈∀≥7Another ExampleevennZaZn ∈∈∀≥,1• Assume the following definition of a recurrence relation:• Prove that all elements in this relation have this property:23,23+=∈∀ ≥iiaaZi01=a22=aWell-Ordering Principle• For any set S of– one or more– integers– all larger than some value• S has a least element8Use this to prove theQuotient 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 uniqueSteps 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 <
View Full Document
Unlocking...