Comp 363 Math Pretest Solutions

1.
f(0)=1
f(1)= 3
f(2)=(2*3)+(1)=6+1=7
f(3)=(2*7)+(3)=14+3=17
f(4)=(2*17)+(7)=34+7=41
41

2a.  Prove by induction:  1 + 3 + 5 + ... + 2n - 1 = n2, for n = 1, 2, 3 ....
Basis: n = 1:  1 = 12 true
Induction step:  assume k >= 1 and  1 + 3 + 5 + ... + 2k - 1 = k2
  show true for k+1:   1 + 3 + 5 + ... + 2(k+1) - 1 = (k+1)2
proof:  1 + 3 + 5 + ... + 2(k+1) - 1
=  [1 + 3 + 5 + ... + (2k - 1)] + 2k + 1
= k2 + 2k + 1  using the induction hypothysis
= (k+1)2

1b. 
Notation: for sets S, T
   #S is the number of elements in S
   S+T is the union of S and T
   S-T is the difference of S and T (elements of S not in T).
   2S is the power set of S, the set of all subsets of S
Prove by induction:  if S is a finite set, then #(2S) = 2#S
Basis n = 0:   The only subset of the empty set is itself.  That is 1 set;  1 = 20
Induction step:  Assume for some k >= 0, that for any set T with k elements,  #(2T) = 2k
Suppose S has  k+1 elements.  We need to show #(2S) = 2k+1
Proof:  S has at least one element, so we can let p be one particular element of S.
Let T = S-{p}, so #T = k.
Let F =  {subsets of S not containing p} = 2T, so by assumption #F = 2k
Let E = {subsets of S containing p}
I claim #E = #F  (explained below) so
#(2S) =  #(F + E) = #F + #E  since E and F are disjoint
= 2(#F) by my claim
=  2(2k) by induction assumption
= 2k+1 

All that remains is to show #F = #E.  There is an obvious relationship between sets in F and E:  For any set f in F there is a set {p}+f in E, and for any set e in E there is a set e - {p} in F.  This means they have the same number of elements.

I will make this a bit more technical for future reference.  There is a 1-1 correspondence between sets E and F in general (and hence they have the same number of elements) if there is a  1-1 function from E into F and a 1-1 function from F into E.    I informally describe two such functions above:  
a:F -> E is defined by a(e) = e + {p};
b:E -> F is defined by b(f) = f - {p}.  

Another way to prove a there is a 1-1 correspondence is to construct a 1-1 function giving the correspondence, from one set onto all of the other.  I did not claim to construct such a correspondence above, but in fact I did.  Also if you have functions a and b that are inverses of each other, then you have a 1-1 correspondence.  You can easily show that functions a and b above are inverses and hence each directly create a 1-1 correspondence.

I asked specifically for an induction proof.  If you take as given that there are 2n n-bit binary numbers (originally proved inductively), then a noninductive 1-1 correspondence proof can easily be made match with a 1-1 correspondence of each subset to an n-bit number by matching each element with an individual bit, which is one if the element is in the subset.
 
3.  Sum   1 + 3 + 32 + 33 + ... + 3n , a geometric series with common ratio 3.
(sum of finite geometric series) = [first term - (last term)*ratio]/(1 - ratio)
= (1 - 3*3n)/(1 - 3) = 0.5(3n+1 - 1)
The part (last term)*ratio can also be thought of as the first term of the continuing series that is omitted.

4.  Consider the statement:  If it is raining, then I carry an umbrella.  (P = "It is raining."; Q = "I carry an umbrella."; P ==> Q)
a.  Converse.  (Q ==> P)  If I carry an umbrella, then it is raining.
b. State the contrapositive.  (~Q ==>  ~P, where ~ means "not")  If  I do not carry an umbrella, then it is not raining.
c.  The original is equivalent to b. (and both are also equivalent to ~P or Q).  (parts a and b together make P <==> Q;  equivalence of P,Q; P iff Q)
(By the way, part a is equivalent to part a's contrapositve, ~P ==> ~Q, but that form is not called the converse of P ==> Q.  I believe it is the obverse(?).)

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 -- the required expression is always true: 
Recall P ==> Q is only false if P is true and Q is false.
A
 B
 C
 A or B
 (A or B)==> C
 B ==> C
 ((A or B)==> C) ==> (B ==> C)
F
 F
 F
 F
 T
 T
 T
F
 F
 T
 F
 T
 T
 T
F
 T
 F
 T
 F
 F
 T
F
 T
 T
 T
 T
 T
 T
T
 F
 F
 T
 F
 T
 T
T
 F
 T
 T
 T
 T
 T
T
 T
 F
 T
 F
 F
 T
T
 T
 T
 T
 T
 T
 T

b.  Basic argument:  To prove P ==> Q, assume P, and derive Q.
1. To show ((A or B)==> C) ==> (B ==> C), assume (A or B) ==> C
1a. We need to show B ==> C.
2. To show B ==> C, assume B
2a.  We need to show C
3. Since B is true by 2, A or B is true.
4. Since A or B is true, C is true by 1, so 2a and 1a are true.

Another approach is using pure Boolean algebra:  Here 'not' is written ~
((A or B)==> C) ==> (B ==> C)
= ~((A or B)==> C) or  (B ==> C)  substituting for P==>Q, ~P or Q
= ~(~(A or B)or C) or  (~B or C)    twice more
= ((A or B) and ~C) or ~B or C       by Demorgan's law
= (((A or B) and ~C) or C) or ~B     regrouping or's
= ((A or B or C) and (~C or C)) or ~B   distributing C
=  ((A or B or C) and true) or ~B     
=  (A or B or C) or ~B
=  A  or C or (B or ~B)
=  A  or C or true = true

6.  How many subsets with 3 elements can be formed from a set of 12 elements?  (You should NOT need to list them all!)
Unordered combinations 12C3 = 12!/(9!*3!) = (12*11*10/(3*2*1) = 220. 
(Subsets are not ordered.  Permutations of 3 (ordered) would be 12P3 = 12!/9! )

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 listing and counting helps!)
Only {2, 6}, {3, 6} share a common factor, making 2 (unordered) pairs.
The total number of pairs is 4C2 = (4*3)/(2*1) = 6.  The proportion sharing common factor = 2/6 = 1/3.
(I was not clear on whether order mattered, but since only distinct pairs were considered it makes no difference:  if you make order matter, both numerator and denominator are multiplied by 2.)
 
8.  Suppose b is a positive number.  If  by = x, then y = logb x  (the inverse function).

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?
Two approaches: 
(1) check is R is reflexive, symmetric, and transitive.  If a relation is NOT an equivalence relation, giving a counterexample to one of the rules is easiest. 
(2) When it IS an equivalence relation, an alternate approach is to guess the partition, in this case {1,4}, {2}, and then check it:
  1. All ordered pairs from the same set in the partition are included in R ({(1,1), (4,4), (1,4), (4, 1)} for {1,4}  and just {(2,2)} for {2})
  2. No pairs from different partitions are included (1or 4 is never paired with 2).  
    (2) can be restated in set notation:  If P is the partition,
⋃
S∈P
S X S  =  R

In this case  R = {1, 4} X  {1, 4} + {2} X {2}
Hence R is the equivalence relation associated with the partition {{1,4}, {2}}.  

10.  (loga b)(logb c) =  loga c  or similarly  logb c =  (loga c)/(loga b)

11.

[
-23
-11
 ] [
2-3
0-4
 ] =





[
-2*2+3*0 -2*-3+3*-4
-1*2+1*0 -1*-3+1*-4
 ] =
[
-4-6
-2-1
 ]