CMSC 250 Homework 9 Fall 2005 0201 0202 Due Wed Nov 2 at the beginning of your discussion section You must write the solutions to the problems single sided on your own lined paper with all sheets stapled together and with all answers written in sequential order or you will lose points 1 For each of the following statements either use induction to prove that the statement is true or give a counterexample with justification to show that it is false a Suppose that the following recurrence relation holds a1 1 a2 0 i Z 2 ai 4ai 1 4ai 2 Prove that n Z an 2n 1 n2 Base Case n 1 n 2 n 1 an a1 1 21 1 12 2 21 1 n 2 an a2 0 22 1 22 2 0 0 IH n i i Z 1 i k 1 ai 2i 1 2i IS i k show ak 2k 1 k2 proof ak 4ak 1 4ak 2 4 2k 1 1 k 1 4 2k 2 1 k 2 2 2 k 2 4 2 2 k 1 4 2k 3 2 k 2 4 2k 3 2 3 k 4 k 4 2k 3 2 k 2k 1 2 k 2k 1 k2 b Suppose that the following recurrence relation holds b1 4 b2 12 i Z 2 bi bi 2 bi 1 Prove that n Z 1 4 bn Base Case n 1 n 2 n 1 bn b1 4 n 2 bn b2 12 4 4 4 12 IH n m m Z 1 m k 4 bm IS n k 1 show 4 bk proof bk bk 2 bk 1 4 bk 2 therefore r Z bk 2 4r 4 bk 1 therefore s Zmb k 2 4s by def of divides bk 4r 4s by substitution bk 4 r s r s Z by closure of Z 4 bk by def of divides c Suppose that the following recurrence relation holds d1 9 10 d2 k Z 3 dk dk 1 dk 2 10 11 Prove that n Z 1 dn 1 Base Case n 1 n 2 9 n 1 dn d1 10 n 2 dn d2 10 11 0 0 9 10 10 11 1 1 IH n i i Z 1 i k di 1 IS n k show dk 1 proof dk dk 1 dk 2 dk 1 1 dk 2 by IH dk 1 1 from above dk 1 dk 2 dk 2 by multiplying both sides by dk 2 dk 2 1 from above dk 1 dk 2 dk 2 1 dk 1 by substitution 2 Use set notation to answer each of the following questions a Suppose A and B are sets defined as A x Z k Z 1 x 4k 1 B x Z k Z 1 x 3k 5 i List 10 elements of A B ii List 10 elements of A B Note A 5 9 13 17 21 25 29 33 37 41 B 8 11 14 17 20 23 26 29 32 35 A B x Z k Z 1 x 12k 17 b For each of the following expressions use a Venn diagram representing the universe U and the two subsets of that universe A and B Shade the part of the diagram that corresponds to the set specified by the expression Note Ac means the complement of A 2 i A ii B c iii A B c iv Ac B c v Ac B c vi A B c 3 4
View Full Document
Unlocking...