InductionSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Introduction to Discrete MathematicsSections 4.1 & 4.2 of [email protected] can we prove the following quantified statement?∀s ∈ SP (x)IFor a finite set S = {s1, s2, . . . , sn}, we can prove that P (x)holds for each element because of the equivalence,P (s1) ∧ P (s2) ∧ · · · ∧ P (sn)IWe can use universal generalization for infinite sets.IAnother, more sophisticated way is to use Induction.NotesWhat is Induction?IIf a statement P (n0) is true for some nonnegative integer; sayn0= 1.IAlso suppose that we are able to prove that if P (k) is true fork ≥ n0, then P (k + 1) is also true;P (k) → P (k + 1)IIt follows from these two statements that P (n) is true for alln ≥ n0. I.e.∀n ≥ n0P (n)This is the basis of the most widely used proof technique:Induction.NotesThe Well Ordering Principle IWhy is induction a legitimate proof technique?At its heart is the Well Ordering Principle.Theorem (Principle of Well Ordering)Every nonempty set of nonnegative integers has a le ast ele me nt.Since every such set has a least element, we can form a base case.We can then proceed to es tablish that the set of integers n ≥ n0such that P (n) is false is actually empty.Thus, induction (both “weak” and “strong” forms) are logicalequivalences of the well-ordering principle.NotesAnother View ITo look at it another way, assume that the statementsP (n0) (1)P (k) → P (k + 1) (2)are true. We can now use a form of universal generalization asfollows.Say we choose an element from t he universe of discourse c. Wewish to establish that P (c) is true. If c = n0then we are done.NotesAnother View IIOtherwise, we apply (??) above to getP (n0) ⇒ P (n0+ 1)⇒ P (n0+ 2)⇒ P (n0+ 3)· · ·⇒ P (c − 1)⇒ P (c)Via a finite number of steps (c − n0), we get that P (c) is true.Since c was arbitrary, the universal generalization is established.∀n ≥ n0P (n)NotesInduction IFormal DefinitionTheorem (Principle of Mathematical Induction)Given a statement P concerning the integer n, suppose1. P is true for some particular integer n0; P (n0) = 1.2. If P is true for some particular integer k ≥ n0then it is truefor k + 1.Then P is true for all integers n ≥ n0, that is∀n ≥ n0P (n)is true.NotesInduction IIFormal DefinitionIShowing that P (n0) holds for some initial integer n0is calledthe Basis Step.IShowing the implication P (k) → P (k + 1) for eve ry k ≥ n0iscalled the Induction Step.IThe assumption P (nk) itself is called the inductive hypothesis.ITogether, induction can be expressed as an inference rule.P (n0) ∧ ∀k ≥ n0P (k) → P (k + 1)→ ∀n ≥ n0P (n)NotesExample IExampleProve that n2≤ 2nfor all n ≥ 5 using induction.We formalize the statement as P (n) = (n2≤ 2n).Our base case here is for n = 5. We directly verify that25 = 52≤ 25= 32and so P (5) is true and thus the basic step holds.NotesExample IContinuedWe now perform the induction step and assume that P (k) (theinductive hypothesis) is true. Thus,k2≤ 2kMultiplying by 2 we get2k2≤ 2k+1By a separate proof, we can show that for all k ≥ 5,2k2≥ k2+ 5k > k2+ 2k + 1 = (k + 1)2Using transitivity, we get that(k + 1)2< 2k2≤ 2k+1Thus, P (k + 1) holdsNotesExample IIExampleProve that for any n ≥ 1,nXi=1i2=n(n + 1)(2n + 1)6The base case is easily verified;1 = 12=(1 + 1)(2 + 1)6= 1Now assume that P (k) holds for some k ≥ 1, sokXi=1i2=k(k + 1)(2k + 1)6NotesExample IIContinuedWe want to show that P (k + 1) is true; that is, we want to showthatk+1Xi=1i2=(k + 1)(k + 2)(2k + 3)6However, observe that this sum can b e writtenk+1Xi=1i2= 12+ 22+ · · · k2+ (k + 1)2=kXi=1i2+ (k + 1)2NotesExample IIContinuedk+1Xi=1i2=k(k + 1)(2k + 1)6+ (k + 1)2(∗)=k(k + 1)(2k + 1)6+6(k + 1)26=(k + 1) [k(2k + 1) + 6(k + 1)]6=(k + 1)2k2+ 7k + 6 6=(k + 1)(k + 2)(2k + 3)6NotesExample IIContinuedThus we have thatk+1Xi=1=(k + 1)(k + 2)(2k + 3)6so we’ve established that P (k) → P (k + 1).Thus, by the principle of mathematical induction,nXi=1i2=n(n + 1)(2n + 1)6NotesExample IIIExampleProve that for any integer n ≥ 1, 22n− 1 is divisible by 3.Define P (n) to be the statement that 3 | (22n− 1).Again, we note that the base case is n = 1, so we have that22·1− 1 = 3which is certainly divisible by 3.We next assume that P (k) holds. That is, we assume that thereexists an integer ` such that22k− 1 = 3`NotesExample IIIContinuedNote that22(k+1)− 1 = 4 · 22k− 1By the inductive hypothesis, 22k= 3` + 1, applying this we get that22(k+1)− 1 = 4(3` + 1) − 1= 12` + 4 − 1= 12` + 3= 3(4` + 1)And we are done, since 3 divides the RHS, it must divide the LHS.Thus, by the principle of mathematical induction, 22n− 1 isdivisible by 3 for all n ≥ 1.NotesExample IVExampleProve that n! > 2nfor all n ≥ 4The base case holds since 24 = 4! > 24= 16.We now make our inductive hypothesis and assume thatk! > 2kfor some integer k ≥ 4Since k ≥ 4, it c ertainly is the case that k + 1 > 2. Therefore, wehave that(k + 1)! = (k + 1)k! > 2 · 2k= 2k+1So by the principle of mathematical induction, we have our desiredresult.NotesExample VExampleLet m ∈ Z and suppose that x ≡ y (mod m). Then for all n ≥ 1,xn≡ yn(mod m)The base case here is trivial as it is encompassed by theassumption.Now assume that it is true for some k ≥ 1;xk≡ yk(mod m)NotesExample VContinuedSince multiplication of corresponding sides of a congruence is stilla congruence, we havex · xk≡ y · yk(mod m)And soxk+1≡ yk+1(mod m)NotesExample VIExampleShow thatnXi=1i3= nXi=1i!2for all n ≥ 1.The base case is trivial since 13= (1)2.The inductive hypothesis will assume that it holds for some k ≥ 1:kXi=1i3= kXi=1i!2NotesExample VIContinuedFactBy another standard induction proof (see the text) the summationof natural numbers up to n isnXi=1i =n(n + 1)2We now consider the summation for (k + 1):k+1Xi=1i3=kXi=1i3+ (k + 1)3NotesExample VIContinuedk+1Xi=1i3=k(k + 1)22+ (k + 1)3=(k2(k + 1)2) + 4(k + 1)322=(k + 1)2k2+ 4k + 4 22=(k + 1)2(k + 2)222=(k + 1)(k + 2)22So by the PMI, the equality holds.NotesExample VIIThe Bad ExampleConsider this “proof” that all of you will receive the same grade.Proof.Let P (n) be the statement that every set of n students receivesthe same grade. Clearly P (1) is true, so the base case is satisfied.Now assume that P (k − 1) is true. Given a group of k students,apply P (k − 1) to
View Full Document
Unlocking...