Discrete Mathematics (Math Problem Sample)

Discrete Mathematics Final Exam Problem 1 * Cn+1 = 2(2n+1)n+2Cn Computing from C0 – C7; * C0 = 1 * C1 = 2(0+1)0+2×1=1 * C2 = 2(2+1)3×1=2 * C3 = 2(4+1)4×2=5 * C4 = 2(6+1)5×5=14 * C5 = 2(8+1)6×14=42 * C6 = 2(10+1)7×42=132 * C7 = 2(12+1)8×132=429 Therefore the catalan numbers are C0 = 1, C1 = 1, C2 = 2, C3 = 5, C4 = 14, C5 = 42, C6 = 132, and C7 = 429. * 1n+12n!2n-n!n!(breakdown of the general form) * C0 = 1 * C1 = 12×2=1 * C2 = 13×6=2 * C3 = 14×20=5 * C4 = 15×70=14 * C5 = 16×252=42 * C6 = 17×924=132 * C7 = 18×3432=429 The answers in (b) are the same as (a) above because numbers are generally derived from 1n+12n!2n-n!n! * If n =0 and it is substituted into the expression given C0 = 1 which is true. Hence, the Basis. Inductive Hypothesis: If the given formula is true for some arbitrary value k, where Ck = 1k+1C2kk Inductive Step: It’s needed to show that the formula holds for k+1. Considering Ck+1, recurrence relation for catalan numbers is; Ck+1 =i=0n1i+12ii×1k-i+12k-ik-i On simplification we have; 2k+1k+1 = 2k+1k+1=2k+0.5k+ 2k+0.5k+1 2k+1k+i= i=0k2ii2k-ik-i The above expression can also be rewritten as; Ck+1 =1k+2i=0k2ii2k-ik-i On application of the above expression to the recursive formula we have; Ck+1 =1k+22k+1k+1 which proves that the formula holds for k+1. Problem 2 * If Q(L) is the product of numbers in the list L. A recursive definition would be in the form; Q(L) = Product of all umbers in the list L = Represents the list of numbers. Base Case: If L is empty (L = []), the multiplicative identity is 1, therefore, Q([])=1. Recursive Step: If L = x:K where x appears to be the first in the list and K the last , products of all elements in L; Q(x:K) = x*Q(k). * [4, 5]; applying the recursive definition, product would be; Q[4, 5] = 4* Q[5] = 4*(5*1) = 4*5 =20 ii) [2,4,8,6]; applying the recursive definition, the product would be; Q[2,4,8,6] = 2*Q([4,8,6]) =2*(4*Q([8,6])) =2*(4*(8*Q[6])) =2*(4*(8*(6*1))) =2*(4*(8*6)) =2*(4*48) =2*192 =384 * Q(L+M) =Q(L).Q(M) Applying induction on list L Base Case: Considering L=[], the concatenation of a list that is empty and M is just M. Thus []++MM = M. Given that Q([]) = 1, the product of concatenated list is; Q([]++M)=Q(M). The product of individual list would be; Q([]) * Q(M) = 1 * Q(M) = Q(M), both sides are equal, therefore, the base case is proven. Inductive step; For a list K the property holds Q(K++M) = Q(k) * Q(M). Considering L=x:K, we have to prove Q((x:K)++M) = Q(x:K) * Q(M) Using the concatenation operator (x:K)++M = x:(K++M). According to the recursive definition, the product of this concatenation is; Q(x:(K++M))=x * Q(K++M) Applying the induction hypothesis to Q(K++M), we get; Q(x:(K++M)) = x *(Q(k) * Q(M)) Applying the recursive step of the definition; Q(x:K) = x * Q(k) x * Q(k) = Q(x:K) The product becomes; Q(x:(K++M)) = (x *Q(k)*Q(M)) =Q(x:K) * Q(M). Therefore, Q(L++M) = Q(L) * Q(M). Problem 3 * 1659 =(24)59 = 2209 = 22.22222 ≅4.67 * 256//17 and 256%17 256÷17 =15(remainder 117) 256%17 = 15r1 =1 Therefore, answers are 15 and 1. * Len([17, 15, 7, 0]) = 4. The length of the list is 4. Problem 4 * ρA×B=A×B=58×44=2552elements Set A×B is the cartesian product of A and B, therefore elements in A × B is the sum of total elements in A and B . ρA×B , ρA×B=2|A×B|=22552 * R:A→B. this is a subset of the Cartesian product A * B. Since A has 58elements and B has 44 elements, Cartesian product A*B would have 58 * 44 = 2552 ordered pairs. Therefore, there are 22552 different relations in R:A→B * For each element a in set A, there are 44 elements in set B to which f can map a because f can map a to any element in B. therefore, there are 4458 ways to define such functions. Problem 5 * (A\B)∩B= ∅ To prove the above, LHS(Left hand side of the expression) must be equal to RHS(Right hand side of the expression) * LHS: (A\B)∩B, this means we have to consider element that can be found in both A\B and B but A\B has only elements from A not in B. Therefore, the intersection with B would be empty. * RHS: ∅, an empty set literally contains no elements in it. Both the LHS and RHS of the expression are empty sets which makes them equal. Hence, (A\B)∩B= ∅ * (B\A) )∩B = B\A * LHS: (B\A) )∩B, this means elements in B\A that are also in B. B\A consists of elements of B that are not in A. So, it’s intersection with B would be B\A. * RHS: B\A. It consist of element in B that are not in A. since LHS = RHS = B\A, (B\A) )∩B = B\A * (A∆B)∩B=B\A LHS: (A∆B)∩B ∆ symmetric difference (A∆B) contains element that are in either A or B but not in both. (A∆B)∩B means elements in both (A∆B) and in B, the intersection with B would be elements of B not in A, which is B\A. RHS, B\A: This includes set of elements in B that are not in A. both LHS and RHS of the expression are equal to B\A they are equal. Hence, (A∆B)∩B=B\A. Problem 6 Considering all condittions i.e reflexive, transitive, symmetric, antisymmetric. * Reflexive: The relation R is said to be reflexive if all the elements belong to itself. In this instance, for every webpage a, there is a need to check if aRa. If everybody who has visited webpage a has also visited webpage a then aRa is true, this makes the relation reflexive. * Symmetric: A relation is said to be symmetric whenever a belongs to b, then b is related to a. In this case, there is a need to check if aRb implies bRa. If everyone who has visited webpage a has also visited webpage b, its not essential that everyone that has visited webpage b has also visited a. therefore, the relation is not symmetric. * Antisymmetric: A relation is said to be antisymmetric if whenever aRa and bRa both hold, then a=b. In this instance, if everyone who has visited webpage a has visited webpage b has also visited webpage a is the same as the set of visitors to webpage b, meaning a=b. Therefore, the relation is antisymmetric. * Transitive: A relation is said to be transitive if whenever aRb and bRc both hol, then aRc. In this instance, if everyone who has visited webpage a has also visited webpage b and everyone who has visited webpage b has also visited c, it implies that everyone who has visited webpage a has also visited webpage c. Therefore the relation is transitive. Conclusively, the relation R on the set of all webpages is; * Reflexive * Symmetric * Antisymmetric * Transitive. Problem 7 * f:Z→N, f(n) = n2. This is not an injective function because f(-x) = f(x) i.e two different elements can produce the same result e.g f(-3) = 9 and f(3) = 9. It is not a surjective function as well because there is no element in Z that can yield 1(impossible to get odd numbers as output), some elements cannot be achieved by this function. A function can only be bijective if and only if it is both surjective and injective, therefore it is not a bijective function. * g:N×N→N, g(m, n) = 3m.5n The function above is injective because every pair of natural numbers(m,n) leads to a unique result in the co-domain. There is no two different pairs that can produce the same product of powers of 3 and 5. It is not surjective. If the result must be a product of powers of 3 and 5, there will be numbers in N that are not obtainable with this function. This function is injective but not surjective, therefore, it is not bijective. * h: Z→Z. h(n) =n-2. The function is injective because if h(a) = h(b), it implies a-2 = b-2 which is the same as a=b. It is surjective because for every x in Z there is an n=x+2 such that h(n) =x. The function is bijective because, it is both injective and surjective Problem 8 An arbitrary set A is given with seven different natural numbers A = {m1, m2, m3,m4,m5,m6, m7} ri → remainder when mi is divided by 5 ri = mi mod5 the set of remainders can be denoted as { r1, r2, r3,r4,r5,r6, r7}. There can only be 5 possible remainders (0, 1, 2, 3, 4...