CS 70 Discrete Mathematics for CSFall 2003 Wagner HW 2Due Thursday September 11Formatting your solution: Please put at the top of your solution the following information: your user-name on cory.eecs, your full name, the string “CS70, Fall 2003, HW #2”, your section number, andyour partners.1. (5 pts.) Any questions?What’s the one thing you’d most like to see explained better in lecture or discussion sections? Aone-line answer would be appreciated.(Sometimes we botch the description of some concept, leaving people confused. Sometimes we omitthings people would like to hear about. Sometimes the book is very confusing on some point. Here’syour chance to tell us what those things were. All feedback is welcome.)2. (20 pts.) Simple inductionProve that 2n< n! for all integers n ≥ 4.3. (20 pts.) Simple inductionProve that 1· 1!+ 2· 2!+ · · · + n· n! = (n+ 1)!− 1 for all integers n ∈ N.4. (15 pts.) A pizza proofWorking at the local pizza parlor, I have a stack of unbaked pizza doughs. For a most pleasingpresentation, I wish to arrange them in order of size, with the largest pizza on the bottom. I know howto place my spatula under one of the pizzas and flip over the whole stack above the spatula (reversingtheir order). This is the only move I know that can change the order of the stack; however, I amwilling to keep repeating this move until I get the stack in order. Is it always possible to get the pizzasin order? Prove your answer.5. (15 pts.) Strong inductionChocolate often comes in rectangular bars marked off into smaller squares. It is easy to break a largerrectangle into two smaller rectangles along any of the horizontal or vertical lines between the squares.Suppose I have a bar containing k squares and wish to break it down into its individual squares. Provethat no matter which way I break it, it will take exactly k− 1 breaks to do this.6. (25 pts.) You be the graderAssign a grade of A (correct) or F (failure) to each of the following proofs. If you give a F, pleaseexplain exactly what is wrong with the structure or the reasoning in the proof. You should justify allyour answers (remember, saying that the claim is false is not a justification).(a) Theorem 0.1: For all positive integers n,∑ni=1i = (n− 1)(n+ 2)/2.Proof: The proof will be by induction.Base case: The claim is valid for n = 1.Induction step: Assume that∑ki=1i = (k− 1)(k + 2)/2. Then∑k+1i=1i =∑ki=1i+ (k + 1). ByCS 70, Fall 2003, HW 2 1the inductive hypothesis,∑k+1i=1i = (k− 1)(k+ 2)/2+ (k+ 1). Collecting terms and simplifying,the right-hand side becomes k(k + 3)/2. Thus∑k+1i=1i = ((k + 1) − 1)((k + 1) + 2)/2, whichcompletes the induction step. 2(b) Theorem 0.2: For every n ∈ N, n2+ n is odd.Proof: The proof will be by induction.Base case: The natural number 1 is odd.Inductive step: Suppose k ∈ N and k2+ k is odd. Then,(k+ 1)2+ (k + 1) = k2+ 2k + 1+ k+ 1 = (k2+ k) + (2k + 2)is the sum of an odd and an even integer. Therefore, (k + 1)2+ (k + 1) is odd. By the Principleof Mathematical Induction, the property that n2+ n is odd is true for all natural numbers n. 2(c) Theorem 0.3: For all x, n ∈ N, if nx = 0 and n > 0, then x = 0.Proof: The proof will be by induction.Base case: If n = 1, then the equation nx = 0 implies x = 0, since nx = 1· x = x in this case.Induction step: Fix k > 0, and assume that kx = 0 implies x = 0. Suppose that (k + 1)x = 0.Note that (k+ 1)x = kx+ x, hence we can conclude that kx+ x = 0, or in other words, kx = −x.Now there are two cases:Case 1: x = 0. In this case, kx = −x = −0 = 0, so kx = 0. Consequently, the inductive hypoth-esis tells us that x = 0.Case 2: x > 0. In this case, −x < 0 (since x > 0). At the same time, kx ≥ 0 (since k,x ≥ 0). Butthis is impossible, since we know kx = −x. We have a contradiction, and therefore Case 2cannot happen.In either case, we can conclude that x = 0. This completes the proof of the induction step. 2(d) Theorem 0.4: For all x, y,n ∈ N, if max(x,y) = n, then x = y.Proof: The proof will be by induction.Base case: Suppose that n = 0. If max(x,y) = 0 and x,y ∈ N, then x = 0 and y = 0, hence x = y.Induction step: Assume that, whenever we have max(x,y) = k, then x = y must follow. Nextsuppose x,y are such that max(x,y) = k+1. Then it follows that max(x− 1,y− 1) = k, so by theinductive hypothesis, x− 1 = y− 1. In this case, we have x = y, completing the induction step.2(e) Theorem 0.5: ∀n ∈ N. n2≤ n.Proof: The proof will be by induction.Base case: When n = 0, the statement is 02≤ 0 which is true.Induction step: Now suppose that k ∈ N, and k2≤ k. We need to show that(k+ 1)2≤ k+ 1Working backwards we see that:(k+ 1)2≤ k+ 1k2+ 2k + 1 ≤ k+ 1k2+ 2k ≤ kk2≤ kSo we get back to our original hypothesis which is assumed to be true. Hence, for every n ∈ Nwe know that n2≤ n. 2CS 70, Fall 2003, HW 2
View Full Document
Unlocking...