Homework answers / question archive / Problem 1

Problem 1

Math

Share With

Problem 1. (10 points) Use mathematical induction to prove that 3n+1-1 1+ 3 + 9 + 27 + ... + 3 = for all n > 0. 2 Solution: 30+1-1 Basis Step: P(0) is true since 1 = = 1 2 3k+1-1 = 2 Inductive Hypothesis: Assume P(k): 1+3+9+ 27 + ... + 3k Inductive Step: P(k) P(k + 1): for every positive integer k. Assuming P(k) it follows that 3k+1_1 1+ 3 + 9 + 27 + ... + 3k + 3k+1 = + 3k+1 2 3k+1 - 1 2.3k+1 + 3(3k+1) - 1 2 Problem 2. (8 points) a. How many ways are there to choose 12 cookies if there are five varieties of cookies (with at least 12 of each kind)? Solution: The solution is the number of a 12-combinations with repetition of 5 objects. C(12 + 5 – 1,5 – 1) = C(16,4) = 1820 ways. b. How many ways are there to arrange the letters in the word COMMUNICATION? Solution: C(13,2) ·C(11,2) ·C(9,2) ·C(7,2) ·C(5,2) 13! = 2!2!2!2!2! Problem 3. (10 points) Let Rand S be symmetric relations on a set X. Prove or disprove that R - S is also symmetric. Solution: If (a,b) ER-S then (a, b) E R and (a, b) ES Since R is symmetric, then (b, a) ER Since S is symmetric, then (b, a) € S Hence, (b, a) ER-S If follows that R - S is symmetric Problem 12. (15 points) a. How many Hamilton circuits are there in Kn? Solution: n! b. For what values of m and n does the complete bipartite graph Km,n have a Hamiltonian cycle. Solution: m = n m, n > 2 c. How many non-isomorphic simple graphs are there with 5 vertices and 3 edges? Solution: 4