U.C. Berkeley – CS70: Discrete Mathematics and Probability Problem Set 3Lecturers: Umesh Vazirani & Christos H. Papadimitriou Due September 15, 2006 at 4:00pmProblem Set 31. Simple Induction Prove that for every n ≥ 2,q1 +p1 + ···√1 (n square roots) is irrational.2. Strengthen induction hypothesis Prove that for all n ≥ 1, all the entries of the matrix1 10 1nare bounded above by n.3. Proofs to GradeGrade the following induction proofs. If you think the proof is incorrect, please explain exa c tly whatis wrong with the str uctur e or the reasoning in the proof. Remember, simply saying that the claim (orthe induction hypothesis is false) is n ot a justification.(a) Claim: (∀n ∈ N)(n2≤ n). Proof:i) Base Case: When n = 1, the statement is 12≤ 1 whcih is true.ii) Induction hypothesis: Assume that k2≤ k.ii) Inductive step: 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 tr ue. Hence, fo r e very n ∈ Nwe know that n2≤ n. ♠(b) Claim: (∀n ∈ N)(7n= 1).Proof: (uses strong induction)Base Case: Certainly 70= 1.Induction hypothesis: Assume that 7j= 1 for a ll 0 ≤ j ≤ k.Inductive step: We need to prove that 7k+1= 1. But,7k+1=(7k·7k)7k−1=(1 ·1)1= 1Hence, by the Principle of Strong Induction, 7m= 1 for all m ∈ N. ♥(c) Claim: For all natural numbers n ≥ 4, 2n< n!.Proof: 24= 16 and 4! = 24, so the statement is true fo r n = 4.Assume that 2n< n! for some n ∈ N. Then 2n+1= 2(2n) < 2(n!) ≤ (n + 1)(n!) = (n + 1)!, so2n+1< (n + 1)!. By the principle of mathematical induction, the statement is true for all n ≥ 4.♣1(d) Claim: All natural numbers are equal.Proof: It is sufficient to show that for any two natural numbers A and B, A = B. Further, it issufficient to show that for all N ≥ 0, if A and B satisfy MAX(A, B) = N then A = B.Proceed by induction on N.Base case: If N = 0, then A and B, being natural numbers , must both be 0. So A = B.Induction Step: Assume that the theorem is true for some value k. Take A and B with MAX(A,B) = k+1. Then MAX((A-1), (B-1)) = k. And hence (A-1) = (B-1). Consequently, A = B. ♦4. Consider the following recursively progra m for a function f :function f(n)if n = 0 return 0else return(f (n −1) + 2n)end functionProve by induction that f(n) = n2+ n.5. Examples for stable marriage algorithm.(a) For the following instance of the stable marriag e problem:Men’s preference list:1 B A C2 C B A3 A C BWomen’s preference list:A 1 2 3B 2 3 1C 3 1 2i. List the rogue couples in the pairing (1, C), (2, B), (3, A).ii. Lis t all the stable pairings.(b) Run the traditional propose a nd reject alg orithm on the following example.Men’s preference list:1 A B C D2 B C A D3 C A B D4 A B C DWomen’s preference list:A 2 3 4 1B 3 4 1 2C 4 1 2 3D 1 2 3
View Full Document
Unlocking...