MATH/EECS 1028 Winter 2019

Final examination
Instructor: S. Datta

Instructions:

1. This is a closed book and notes examination. Please put away all books, papers, cell
phones and other electronic devices. Calculators are NOT allowed.

2. Check that this examination has 12 pages, with 22 questions together worth 84 points.

3. You should have received separately, 2 pages containing formulae.

4. You have 180 minutes to complete the exam. Use your time judiciously.

5. Partial credit will be given only if you show some progress in obtaining the answer.
MATH/EECS 1028 Final examination page 2 of 12

1. (1 point) Is the following statement true?

{a, b} ⊆ {{a}, b, c}

2. (2 points) Write down the power set of {a, {{b}}}.

3. (2 points) Enumerate the set {a, b} × {{a}, {b}}.

4. (2 points) For x > 0, x ∈ R, find

(log 1 5)(log5 x)
x
MATH/EECS 1028 Final examination page 3 of 12

5. (4 points) Evaluate
n X
X i
(2k+1 − 2k ).
i=0 k=0

6. (4 points) Suppose that A, B, C are sets and g : A → B and f : B → C are functions.

Show that if f ◦ g is onto, then f must also be onto.
MATH/EECS 1028 Final examination page 4 of 12

7. (4 points) Find ∪∞ ∞
i=1 Ai and ∩i=1 Ai if i ∈ N and Ai = {x|x ∈ Z, −i ≤ x ≤ i}. Write a 1
sentence justification for each answer.

8. (4 points) Prove that if n is an integer, then 3n2 + n + 14 is even.

MATH/EECS 1028 Final examination page 5 of 12

9. (3 points) Let p, q, r be propositions. Show that (p → q) ∧ (q → r) → (p → r) is a

tautology.

10. (3 points) Let S(x) be the predicate “x is a student”, F (x) the predicate “x is a faculty
member”, and A(x, y) the predicate “x has asked y a question”. Let the domain be
all people associated with York University. Use quantifiers to express the following
statement: “Every faculty member has asked some other faculty member a question”.
Do not use any other predicates.

11. (5 points) For the statement “There is a student who has never asked any faculty mem-
ber any questions”, write down the statement in Predicate logic using only the predicates
given in the previous question. Then negate the statement in Predicate logic and simplify
fully. Then translate the negated statement into an English sentence.
MATH/EECS 1028 Final examination page 6 of 12

12. (6 points) Write expressions for the following in Predicate Logic (defining your predi-
cates) and then determine if the inference is valid. If it is, you must indicate the rules
used. If it is invalid you must indicate why.
Doug, a student in this class, knows how to program in Java. Everyone who knows how
to program in Java can get a high-paying job. Therefore, someone in this class can get
a high-paying job.

13. (5 points) Given 12 different 2-digit numbers, show that one can choose two of them so
that their difference is a two-digit number with identical first and second digit (we allow
0 to be written as 00 in this question).
Hint: Any 2 digit number with identical digits is divisible by 11.
MATH/EECS 1028 Final examination page 7 of 12

14. (5 points) Prove using induction that 3 divides n3 + 2n for every positive integer n.

15. (5 points) Consider the sequence defined as d1 = 1, d2 = 2, d3 = 3 and dn+3 = dn+2 +

dn+1 + dn for all positive integers n.
Prove using strong induction that for all positive integers n, dn < 2n .
MATH/EECS 1028 Final examination page 8 of 12

16. (4 points) How many different ways are there to choose a dozen donuts from the 21
varieties at a donut shop? Give a 1-sentence justification.

√
17. (3 points) What is the term independent of x in ( x2 + x)9 ?

18. (3 points) The fourth row of Pascal’s triangle is 1, 4, 6, 4, 1. Write down the fifth row
and write down the value of k for which the numbers you wrote represents the binomial
coefficients for (x + y)k .
MATH/EECS 1028 Final examination page 9 of 12

19. (5 points) Prove that the function f (x) = x + 4 is a bijection from Z to Z. Why is it
not a bijection from N to N?

20. (4 points) In the five-sided star shown, the letters A, B, C, D, and E are replaced
by the numbers 3, 5, 6, 7, and 9, although not necessarily in this order. The sums
of the numbers at the ends of the line segments AB, BC, CD, DE, and EA form an
arithmetic sequence, although not necessarily in that order. What is the middle term
of the arithmetic sequence? Hint: You do not need to construct the sequence to answer
the question.
MATH/EECS 1028 Final examination page 10 of 12

21. (5 points) How many bit strings contain exactly eight 0’s and ten 1’s if every 0 must be
immediately followed by a 1? Justify your answer.

2
22. (5 points) Prove the identity nr=0 nr = 2n
P

n
using a combinatorial (counting) proof,
where n, r are natural numbers and 0 ≤ r ≤ n.
MATH/EECS 1028 Final examination page 11 of 12

Use this page if you need extra space

MATH/EECS 1028 Final examination page 12 of 12

Use this page if you need extra space