CS 111 University of California Riverside Discrete Mathematics Project

Description

1 attachmentsSlide 1 of 1attachment_1attachment_1

Unformatted Attachment Preview

Krzysztof Brzȩczyszczykiewicz SID 834322002
Venkataratnam Narasimha Rattaiah SID 854377890
CS 111 ASSIGNMENT 127
due Friday, February 13
Problem 1: Consider a sequence defined recursively as a0 = 4, a1 = 9, and an = an−1 + 3an−2 for
n ≥ 2. Prove that an = O(2.5n ).
Solution 1: We first prove by induction that an ≤ 4(2.5)n is true.
Base step: In the base step we verify the inequality for n = 0, 1. For n = 0 we have a0 = 4 and
4(2.5)0 = 4, so a0 ≤ 4(2.5)0 . For n = 1 we have a1 = 9 and 4(2.5)1 = 10, so a1 ≤ 4(2.5)1 .
Inductive step: The inductive hypothesis is that an ≤ 4(2.5)n is true for n = 0, 1, …, k, where k ≥ 1.
To complete the inductive step, we need to show that ak+1 ≤ 4(2.5)k+1 .
Since ak ≤ 4(2.5)k and ak−1 ≤ 4(2.5)k−1 holds, we have
ak+1 = ak + 3ak−1
≤ 4(2.5)k + 3 · 4(2.5)k−1
≤ 4(2.5)k−1 (2.5 + 3)
≤ 4(2.5)k−1 (2.5)2
≤ 4(2.5)k+1 .
That is, we have shown that if the inductive hypothesis is true, then ak+1 ≤ 4(2.5)k+1 is also true.
This complete the inductive step.
We thus have an ≤ 4(2.5)n | for all n ≥ 0. Therefore an = O(2.5n ), completing the proof.
Problem 2: Suppose we have three sets, A1 , A2 , A3 with the following properties:
(a) |A2 | = 2|A1 |, |A3 | = 4|A1 |,
(b) |A1 ∩ A2 | = 2, |A1 ∩ A3 | = 2, |A2 ∩ A3 | = 5,
(c) |A1 ∩ A2 ∩ A3 | = 1
(d) |A1 ∪ A2 ∪ A3 | = 27.
Use the inclusion-exclusion formula to determine the number of elements in A1 ∪ A1 ∪ A3 . Show
your work.
Solution 2: We have
|A1 ∪ A2 ∪ A3 | = |A1 | + |A2 | + |A3 | − |A1 ∩ A2 | − |A1 ∩ A3 | − |A2 ∩ A3 | + |A1 ∩ A2 ∩ A3 |
27 = |A1 | + |A2 | + |A3 | − 2 − 2 − 5 + 1
|A1 | + |A2 | + |A3 | = 35
|A2 | = 2|A1 |
|A3 | = 4|A1 |
1
By solving the above equations, we get the cardinalities of A1 , A2 and A3 :
|A1 | = 5
|A2 | = 10
|A3 | = 20
Problem 3: We are given an array A[0, …, n−1] that contains distinct numbers sorted in increasing
order, that is A[i] < A[i + 1] for all i = 0, ..., n − 2. Consider the algorithm below, described in pseudo-code 1 i Purchase answer to see full attachment Tags: IT CSS discrete mathematics User generated content is uploaded by users for the purposes of learning and should be used following Studypool's honor code & terms of service.