计算机导论代写 | CSE 105 Winter 2021 Homework 1

这个作业是完成计算机导论相关的习题
CSE 105 Winter 2021
Homework 1

1. (10 points)
Using proof by contradiction show that for any positive real numbers x, y that x + y ≥ 2
√xy.
2. (10 points)
Show using induction that the sequence defined recursively by a0 = 1 and an = 3an−1 + 1 satisfies the
formula
an =
3
n − 1
2
.
3. (10 points)
Prove that sets A and B are equal if
(A
C ∩ B) ∪ (A ∩ B
C ) = ∅.
4. (10 points)
Give a regular expression for each of the following languages. Include brief justification of your answers.
(a) The set of binary strings that start and end with different characters.
(b) The set of words in the alphabet {a, b, c} in which every c is followed by at least one b or by at
least two a’s.
(c) The set of binary strings of odd length.
(d) The set of strings in the alphabet {a, b, c} which contain at most 2 c’s.
(e) The set of binary strings that start and end with 1.