CS70, Fall 2003 Discussion #2 Amir KamilUC Berkeley 9/5/03Topics: Administrivia, Simple Induction, Bad Proofs, Strong Induction1 Administrivia• Do NOT turn in homework in class. Turn it in the homework box in 283 Soda.• If you come to office hours and I’m not there, check 566 Soda (my office).2 Simple InductionConsider the claim “nn> n! for all natural numbers n > 1.” If the claim is false, then it may be easy todisprove it, since only a single counterexample needs to be found. If it is true, however, it is hard to proveso. One way to prove such a claim is by induction. It is necessary only to prove that the claim is true for thesmallest number in the set of numbers for which it claims to be true, and that if it is true for one numberin the set, it is true for the next number.So let’s actually get around to proving the claim. The first thing that must be done in an inductive proofis to write a proposition that depends on an input. For example, we can writeP (n) = nn> n!.Then our claim in terms of the proposition is∀n ∈ N. n > 1 =⇒ P (n).Now all we have to do is prove that P (n) is true for the 2 (the base case), and if it is true for n, it is truefor n + 1 (the inductive step). (Note that there is a small technicality we are ignoring. The previous twosteps only prove that the proposition n > 1 =⇒ P (n) is true if the antecedent is true. However, since animplication is always true when the antecedent is false, we can ignore that case.)Theorem 2.1: ∀n ∈ N. n > 1 =⇒ P (n)Proof by induction:• Base case: n = 222> 2!, i.e. 4 > 2 is true.• Inductive step:We need to show that P (n) =⇒ P (n + 1), or nn> n! =⇒ (n + 1)n+1> (n + 1)!. By the inductivehypothesis, nn> n!. Then1. nn> n!2. (n + 1)nn> (n + 1)n! multiplying by n + 1, since n + 1 > 03. (n + 1)n> nnsince a > b =⇒ ac> bcwhen a, b, and c are positive4. (n + 1)n+1> (n + 1)nnmultiplying by n + 1, since n + 1 > 05. (n + 1)n+1> (n + 1)n! by transitivity of inequalities6. (n + 1)n+1> (n + 1)! by definition of factorialThus by the principle of induction, the claim is true.Note that induction is not always the best way to approach a proof. Consider the slightly modified claim“n3n3< n! for all natural numbers n > 0.” If you try writing an inductive proof for this claim, you will seethat it is not that easy. In fact, it is much easier to write a proof by arbitrary example for this claim.13 Bad ProofsSo we’ve already “proven” that 2 = 1. This time, let’s prove an even stronger claim: “all natural numbersgreater than or equal to 1 are equal to 1.” In terms of the propositionP (n) = n = 1,our claim is∀n ∈ N. n ≥ 1 =⇒ P (n).Here’s the proof:Claim: ∀n ∈ N. n ≥ 1 =⇒ P (n)Proof by induction:• Base case: n = 11 = 1 is true.• Inductive step: n = 1 =⇒ n + 1 = 11. Suppose n + 1 = 1.2. Then (n + 1) · (n − 1) = n − 1, since a = b =⇒ a · c = b · c.3. Then n2− 1 = n − 1, by the distributive property.4. Then n2= n, since a = b =⇒ a + c = b + c.5. Then 1 = 1, by the inductive hypothesis (substituting 1 for n).6. This is true, so n = 1 =⇒ n + 1 = 1.Therefore, by the principle of induction, ∀n ∈ N. n ≥ 1 =⇒ P (n).Is anything wrong with the above proof? (Of course, since otherwise it wouldn’t be in the section entitled“Bad proofs.”) Can you find the bug in the proof?The error in the proof is an example of a converse error for proofs. In the inductive step, it starts withthe conclusion and derives the premise. This is similar to using Q =⇒ P to try to prove that P =⇒ Q. It isnot valid to do so.In some cases, the steps in such a proof can be reordered to result in a valid proof. In this case, however,reordering the steps results in division by zero in the place of the multiplication by zero in step 2, invalidatingthe proof.There are multiple examples of bad inductive proofs. Some are just stylistically bad, such as a proofthat is composed completely of symbols. Each step in a proof should be part of an English sentence, andshould be justified rigorously. Examples of real fallacies in inductive proofs include the converse e rror above,ignoring or otherwise making a m istake in the base case, and the same logical errors that affect non-inductiveproofs. Be careful not to fall for any of these in your pro ofs.4 Strong InductionConsider the following claim: “all natural numbers greate r than 1 can be expressed as the sum of primes.”Let’s attempt to prove this claim inductively. First, define the propositionP (n) = n can be express ed as the sum of primes.Then the above claim is∀x ∈ N. x > 1 =⇒ P (x).2Now unfortunately, 1 is not a prime number, so P (x) does not immediately imply P (x + 1). However, 2 isa prime number, so P (x) obviously implies P (x + 2). So let’s consider a new propositionQ(n) = P (n) ∧ P (n − 1)Then the above claim is∀x ∈ N. x > 2 =⇒ Q(x).Now we can prove the claim using induction.Theorem 2.2: ∀x ∈ N. x > 2 =⇒ Q(x).Proof by induction:• Base cases: Q(3) = P (2) ∧ P (3)Trivially true, since 2 and 3 are prime, and the can be expressed as the sum of themselves.• Inductive step:We need to show that Q(n) =⇒ Q(n + 1), or P (n − 1) ∧ P (n) =⇒ P (n) ∧ P (n + 1) by substition. P (n)is true from applying and-elimination to the inductive hypothesis Q(n) = P (n − 1) ∧ P (n). Now n + 1can be expressed as (n − 1) + 2. By the inductive hypothesis, n − 1 can be expressed as a sum of somek primes p1+ · · · + pk. As such, n + 1 can be expressed as the sum of the k + 1 primes p1+ · · · + pk+ 2.Thus P (n + 1). Since P (n) and P (n + 1), by and-introduction, Q(n + 1).Since the base case and the inductive step are true, by the principle of induction, we have proven the claim.This technique can be generalized by not only adding P (n− 1) to the proposition Q(n), but also P (n− 2),P (n−3), · · · up to the base case P (2). Then we have to prove the implication that P (2)∧P (3)∧· · ·∧P (n) =⇒P (2) ∧ P (3) ∧ · · · ∧ P (n) ∧ P …
View Full Document
Unlocking...