CPS 102: Discrete Mathematics Instructor: Bruce MaggsAssignment 2 Due: Friday September 28, 20071 Inductive Reasoning (30 points)Write a computer program to draw a two-dimensional space filling c urve. Turn in your code and asample of your output.2 Methods of Proof (5 points)Prove that the square of an even number is an even number using(a) a direct proof.(b) an indirect proof.(c) a proof by contradiction.3 Methods of Proof (5 points)Prove that if n is an integer and 3n + 2 is even, then n is even using(a) an indirect proof.(b) a proof by contradiction.4 Methods of Proof (5 points)Use a proof by cases to show that bn/2cbn/2c = bn2/4c for all integers n.5 Methods of Proof (5 points)Prove or disprove that given a positive integer n, there are n consecutive odd positive integers thatare primes.16 Mathematical Induction (5 points)Find a formula for11.2+12.3+ . . . +1n(n + 1)by examining the values of this expression for small values of n. Use mathematical induction toprove your result.7 Mathematical Induction (5 points)Prove that 1.1! + 2.2! + . . . + n.n! = (n + 1)! − 1 whenever n is a positive integer.8 Mathematical Induction (5 points)Use mathematical induction to prove that1.2.3 + 2.3.4 + . . . + n(n + 1)(n + 2) = n(n + 1)(n + 2)(n + 3)/49 Mathematical Induction (5 points)Prove that1 +14+19+ . . . +1n2< 2 −1nwhenever n is a positive integer greater than 1.10 Mathematical Induction (10 points)Use mathematical induction to prove that a set with n elements has n(n − 1)(n − 2)/6 subsetscontaining e xactly three ele ments whenever n is an integer greater than or equal to 3.11 Mathematical Induction (10 points)Prove that if A1, A2, . . . , Anand B1, B2, . . . , Bnare sets such that Ak⊆ Bkfor k = 1, 2, . . . , n, then(a)Snk=1Ak⊆Snk=1Bk(b)Tnk=1Ak⊆Tnk=1Bk212 Mathematical Induction (5 points)Use the formula for the sum of the terms of a geometric progression to evaluate the following sums.(a) 4 + 4.3 + 4.32+ . . . + 4.38(b) 3 + 3.22+ 3.24+ . . . + 3.210(c) 1 − 2 + 22− 23+ . . . + (−1)n2n13 Mathematical Induction (10 points)Find the flaw with the following “proof” that an= 1 for all nonnegative integers n, whenever a isa nonzero real numb er.BASIC STEP: a0= 1 is true by the definition of a0.INDUCTIVE STEP: Assume that ak= 1 for all nonnegative integers k with k ≤ n. Then notethatan+1=an.anan−1=1.11= 114 Mathematical Induction (10 points)Show that the following form of mathematical induction is a valid method to prove that P (n) istrue for all positive integers n.BASIC STEP: P (1) and P (2) are true.INDUCTIVE STEP: For each positive integer n, if P (n) and P (n +1) are b oth true, then P (n + 2)is true.15 Recursive Definitions (5 points)Find f(1), f(2), f (3), f(4) and f(5) if f(n) is defined recursively by f(0) = 3 and for n = 0, 1, 2, . . .(a) f(n + 1) = −2f(n)(b) f(n + 1) = 3f(n) + 7(c) f(n + 1) = f(n)2− 2f(n) − 2(d) f(n + 1) = 3f(n)/3316 Recursive Definitions (5 points)Give a recursive definition of the sequence {an}, n = 1, 2, 3 . . . if(a) an= 4n − 2(b) an= 1 + (−1)n(c) an= n(n + 1)(d) an= n217 Recursive Definitions (5 points)Show that each of the following proposed recursive definitions of a function on the set of positiveintegers does not produce a well-defined function(a) F (n) = 1 + F (bn/2c) for n ≥ 1 and F (1) = 1(b) F (n) = 1 + F (n − 3) for n ≥ 2 , F (1) = 2 and F (2) = 3(c) F (n) = 1 + F (n/2) for n ≥ 2 , F (1) = 1 and F (2) = 2(d) F (n) = 1 + F (n/2) if n is even and n ≥ 2, F (n) = 1 − F (n − 1) if n is odd, and F (1) = 1(e) F (n) = 1 + F(n/2) if n is even and n ≥ 2, F (n) = F (3n − 1) if n is odd and n ≥ 3 , F (1) =
View Full Document
Unlocking...