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
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 = n2, for n = 1, 2, 3 ....
b.  There are 2n subsets of a set of n elements, for n = 0, 1, 2, ....

3.  Express the sum in a closed-form expression:   1 + 3 + 32 + 33 + ... + 3n

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  by = 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  loga b, loga c, and logb c?

11.  Multiply the matrices  (not in any specific prereq - just checking on this common math topic which may be useful)

] [