# CS 111 University of California Riverside Discrete Mathematics Project

Description

1 attachmentsSlide 1 of 1attachment_1attachment_1

Unformatted Attachment Preview

Krzysztof Brzȩ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
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.

## Reviews, comments, and love from our customers and community:

This page is having a slideshow that uses Javascript. Your browser either doesn't support Javascript or you have it turned off. To see this page as it is meant to appear please use a Javascript enabled browser. Peter M.
So far so good! It's safe and legit. My paper was finished on time...very excited! Sean O.N.
Experience was easy, prompt and timely. Awesome first experience with a site like this. Worked out well.Thank you. Angela M.J.
Good easy. I like the bidding because you can choose the writer and read reviews from other students Lee Y.
My writer had to change some ideas that she misunderstood. She was really nice and kind. Kelvin J.
I have used other writing websites and this by far as been way better thus far! =) Antony B.
I received an, "A". Definitely will reach out to her again and I highly recommend her. Thank you very much.  