CS 70 Discrete Mathematics for CSFall 2003 Wagner Lecture 2This lecture covers induction, which is the most common technique for proving universally quantified sen-tences over the natural numbers and other discrete sets of objects (lists, trees, tilings, graphs, programs, etc.).We need induction, or something like it, because any attempt at proof by enumeration of possible worldsis doomed to failure—with infinitely many objects, there are infinitely many possible worlds that can bedefined.The principle of inductionThe principle of induction is an axiom of the natural numbers. Recall from Lecture 1 that the naturalnumbers satisfy Peano’s axioms (where we have written n+ 1 instead of s(n) for clarity):0 is a natural numberIf n is a natural number, n+ 1 is a natural numberThese axioms don’t quite define the natural numbers, because they include no statement of the kind, “...and by the way, there are no other natural numbers.” This makes it impossible to use these axioms alone toprove that any property holds for all natural numbers n.The principle of induction essentially fills this gap. Informally, it says the following:If you can prove that some property holds for 0, and you can prove that the property holds forn+ 1 if it holds for n, then you have proved that the property holds for all the natural numbers.To state this principle formally, let P(n) be an arbitrary proposition about the natural number n. (For exam-ple, P(n) might be “2n> n”.) The principle of induction is as follows:Axiom 2.1 (Induction): For any property P, if P(0) and ∀n∈N (P(n) =⇒ P(n+ 1)), then ∀n∈N P(n).This says that if P(0) holds, and P(0) =⇒ P(1), and P(1) =⇒ P(2), and so on, then P(n) must be truefor all n. This seems pretty reasonable. (Later we will see that the axiom has an alternative form that seemseven more reasonable.)Inductive proofsThe standard first example is to verify the well-known formula for the sum of the first n positive integers:Theorem 2.1: ∀n∈Nn∑i=1i = n(n+ 1)/2[Note:∑ni=1i means 1 + 2 + ·· · + n but is more precise. When n = 0 the summation has no terms so is 0;when n = 1 it has just the term i = 1 so the sum is 1.]In many, but not all, cases of proof by induction, the property P used in the induction is exactly the one wewant to prove. That is the case here: P(n) is the proposition that∑ni=1i = n(n+ 1)/2.CS 70, Fall 2003, Lecture 2 1To construct an inductive proof, first we need to establish the base case P(0), then we need to prove thatBASE CASEP(n+ 1) follows from P(n). The latter proof is called the inductive step, and usually involves all the work.INDUCTIVE STEPThe key idea of induction, though, is that this step is easier than proving the whole universal propositionfrom scratch because you get to assume that P(n) is true when proving P(n+ 1). This assumption is calledthe inductive hypothesis.INDUCTIVEHYPOTHESISProof: The proof is by induction over the natural numbers.• Base case: prove P(0).P(0) is the proposition∑0i=1i = 0(0+1)/2. By the definition of summation, this is equivalent to 0= 0,which is true.• Inductive step: prove P(n) =⇒ P(n+ 1) for all n∈ N.1. The inductive hypothesis isn∑i=1i = n(n+ 1)/2.2. To prove:n+1∑i=1i = (n+ 1)(n+ 2)/2.3. Re-expressing the summation for n + 1 in terms of the summation for n (for which we have theformula), we haven+1∑i=1i = n∑i=1i!+ (n+ 1) by the definition of summation= n(n+ 1)/2+ (n+ 1) using the inductive hypothesis= n(n+ 1)/2+ 2(n+ 1)/2 = (n+ 1)(n+ 2)/2Hence, by the induction principle, ∀n∈ Nn∑i=1i = n(n+ 1)/2. 2This example shows the format of an inductive proof, which you should follow religiously. It also exhibitsthe technique common to all inductive proofs: the proposition P(n+1) is reformulated into a part that comesdirectly from P(n), for which we already have the answer, and an “extra bit” that is then combined with theanswer from P(n) to give the answer for P(n+ 1).Example proofsTheorem 2.2: ∀n∈N, n3− n is divisible by 3.It will be helpful to define “divisible by” more precisely. We write a|b (a divides b, or b is divisible by a);the definition isDefinition 2.1 (Divisibility): For all integers a and b, a|b if and only if for some integer q, b = aq.As in the previous example, we take the definition of P straight from the theorem; P(n) is the propositionthat 3|(n3− n).Proof: The proof is by induction over the natural numbers.• Base case: prove P(0).P(0) is the proposition that 3|(03− 0) or 3|0, which is true from the definition of divisibility withq = 0.CS 70, Fall 2003, Lecture 2 2• Inductive step: prove P(n) =⇒ P(n+ 1) for all n∈ N.1. The inductive hypothesis is 3|(n3− n), or n3− n = 3q for some integer q.2. To prove: 3|((n+ 1)3− (n + 1)). We do this by showing that (n+ 1)3− (n + 1) = 3r for someinteger r.3. Re-expressing the quantity for n + 1 in terms of the quantity for n (for which we know a simpleformula), we have(n+ 1)3− (n+ 1) = n3+ 3n2+ 3n+ 1− (n+ 1) expanding out the cubic term= (n3− n) + 3n2+ 3n rearranging to isolate the known quantity= 3q+ 3(n2+ n) = 3(q+ n2+ n)4. Hence, since q and n are integers, we have 3|((n+ 1)3− (n+ 1)).Hence, by the induction principle, ∀n∈ N 3|(n3− n). 2Again, the trick is to reduce P(n+ 1) to P(n) and a little extra fact; here the little extra fact is that 3|(3n2+3n). Sometimes, this step can be carried out by simple manipulation to pull P(n) out of P(n+1); sometimes,you really have to understand what’s going on at a deep level.The next example proves an inequality between two functions of n; such inequalities are useful in computerscience when showing that one algorithm is more efficient than another. Notice that the base case is P(2)rather than P(0). This is an obvious variant1of the standard principle of induction; we can begin with anyfixed integer to show that all subsequent integers satisfy some property. (If we want to prove P(n) for allintegers, including negative ones, we must do two inductions—one upwards from, say, 0 and one downwardsfrom 0.)Theorem 2.3: ∀n∈N n > 1 =⇒ n! < nnProof: The proof is by induction over the natural numbers greater than 1.• Base case: prove P(2).P(2) is the proposition that 2! < 22, or 2 < 4, which is true.• Inductive step: prove P(n) =⇒ P(n+ 1) for all natural numbers n > 1.1. The inductive hypothesis is n! < nn.2. To prove: (n+ 1)! < (n+ 1)(n+1)3. Re-expressing the quantity for n + 1 in terms of the quantity for n (for which we
View Full Document
Unlocking...