MATH 211 Final, Fall 2005
American University of Beirut · Discrete Structures · 10 pages
More MATH 211 files
Show the text of this final exam
AMERICAN UNIVERSITY OF BEIRUT
Faculty of Arts and Sciences
Mathematics Department
MATH 211
FINAL EXAMINATION
FALL 2005-2006
Closed Book, 2 HOURS
WRITE YOUR ANSWERS ON THE QUESTION SHEET
STUDENT NAME
ID NUMBER
Problem
Out of
Grade
1
10
2
10
3
10
4
10
5
10
6
10
TOTAL
60
1
1. (10 points)
(a) (3 points) Prove without using truth tables that the implication
(¬q ∧ (p → q)) → ¬p,
is a tautology.
(b) (5 points) Let a, b, c be any three consecutive positive integers. Prove that a3 +
b3 + c3 is divisible by 9
(c) (2 points) Let P(x) and Q(x) be predicates on a universal set U = {x1, x2}. Prove
the equivalence :
(∀x (P(x) ∧ Q(x))) ≡ (∀x P(x)) ∧ (∀x Q(x)).
2
2. (10 points) Let M = 2p − 1, (p ∈ N ).
(a) (3 points) Show that M prime implies that p is prime.
(b) (3 points) Let N = (2p − 1)2p−1, where p is prime. Give the elements of the set
SN that consists of the divisors of N, others than N :
SN = {x1, x2, ..., xn},
with {∀i = 1, 2...n : xi|N, xi ̸= N}. What is the cardinality of SN.
3
(c) (2 points) Show that
n
�
i−1
xi = N.
(d) (2 points) Give N and SN for p = 2, 5
4
3. (10 points) Consider the recurrence relation :
an − 5an−1 + 6an−2 = 2n + 3n, a0 = 0, a1 = 1.
(1)
(a) (4 points) Find the general solution of the recurrence equation :
an − 5an−1 + 6an−2 = 0.
(b) (4 points) Find a particular solution to :
an − 5an−1 + 6an−2 = 2n + 3n.
(Hint : find first particular solutions for each of 2n and 3n).
(c) (3 points) Find the solution to the recurrence relation (1)
5
4. (10 points) Given a sequence of n + 1 real numbers {a(0), a(1), ..., a(n)} and a real
number c, consider the following algorithm :
y :=a(0)
p :=1
for i from 1 to n
p :=p*c
y :=y+a(i)*p
end
(a) (4 points) Give f(n) the number of artithmetic operations needed to execute this
algorithm.
(b) (2 points) Give α in f(n) = Θ(nα).
(c) (4 points) (independent from (a) and (b)) Assume that f(n) = Θ(n3) and g(n) =
Θ(n). Give Θ(f(n) + g(n)) and Θ( f(n)
g(n)).
6
5. (10 points) Let S be a set with n elements. Answer the following justifying your answer.
(a) (2 points) How many ordered pairs are there in S × S ?
(b) (3 points) How many relations are there on S (subsets of S × S) ?
(c) (5 points) Let A, B, C be 3 sets. Suppose |A| = |B| = |C| = 100, |A ∩ B| = 70,
|A ∩ C| = 50, |B ∩ C| = 45 and |A ∪ B ∪ C| = 175. How many elements are there
in A ∩ B ∩ C ?
7
6. (10 points) Let n ∈ N+.
(a) (3 points) Let Sn be the set of all non-empty subsets, {a1, a2, ..., ak|1 ≤ k ≤ n}
of the set of first n integers {1, 2, ..., n}. Give a recursive definition of the sets Sn.
Indicate the basis and recursive steps.
Hint : The recursive step should include 3 cases.
(b) (2 points) Let
sn = Σ{a1,a2,...,ak}∈Sn(
1
a1.a2...ak−1.ak
).
Give the expressions and values of s1, s2 and s3.
8
(c) (5 points) Prove by Mathematical induction that sn = n.
9
Additional space for answers
10