Comp 363 Math Pretest
Due at the beginning of the second class meeting.
Try to do these problems without references. If that
does
not work,
please look at a discrete math or algebra reference. If you
use
references, say what you used, and how. Examples:
Used reference ___ and
- looked up ___ formula
- checked my solution and left it as is
- checked and modified ___ in my solution
- went over the ___ idea, and then did the problem myself
- followed along with an example in the reference
- ...
Do not just copy from a reference in any case.
Your number of correct responses does NOT count in your grade. I
do expect you to work on all
of the problems. The results are
important for me to plan how the class is run. I do not promise
all the exact problems will be relevant for Comp 363, but they help me
get a feeling for your mathematical and logical background.
1. If f(0) = 1, f(1) = 3, and f(n) = 2*f(n-1) + f(n-2) for n = 2,
3, 4, ..., what is f(4)?
2. Prove each by formal induction, not some other proof technique:
a. 1 + 3 + 5 + ... + 2n - 1 = n^{2},
for n = 1, 2, 3 ....
b. There are 2^{n} subsets of a set of n elements, for n
= 0, 1, 2, ....
3. Express the sum in a closed-form expression: 1 + 3 + 3^{2} + 3^{3} + ... + 3^{n}
4. Consider the statement S: If it is raining, then I carry
an umbrella.
a. State the converse of S.
b. State the contrapositive of S.
c. Which of these answers are equivalent to S? (a, b, both, or
neither?)
5. Let A B, and C be Boolean expressions, and assume '==>'
means 'implies'. Consider the statement S:
[(A or B) ==> C] ==> (B ==> C)
a. Prove S with a truth table.
b. Prove S with a logical argument, giving a reason for each step (assuming a hypothesis and deriving the conclusion)
6. How many subsets with 3 elements can be formed from a set of
12 elements? (You should NOT need to list them all!)
7. Suppose a pair of distinct elements are chosen at random from
the set (2, 3, 5, 6). What is the probability that both numbers
share a common factor > 1? (Here some listing and counting helps!)
8. Suppose b is a positive number. If b^{y}
= x, what is y in terms of b and x?
9. Is R = {(1,1), (2,2), (4,4), (1,4), (4, 1)} an equivalence
relation on the set S = {1, 2, 4}? If not, what rule is
broken? If so, how is S partitioned by R?
10. What is an identity relating log_{a} b, log_{a} c, and log_{b} c?
11. Multiply the matrices (not in any specific prereq - just checking on this common math topic which may be useful)