Homework 7, Due Tuesday, November 8.

 Write a definition for the following sequences: (half credit for
   correct recursive definitions).  You do not need to do anything
   with the explanations given.

(a) 64, 60, 56, 52, 48, 44, 40 ...
    (the number of different possible 2 card hands that give blackjack
    when there are zero, one, two, etc... of the 10 valued cards
    removed from the deck)

f(x) = 64 - 4x.
note, this sequence starts with x = 0.

(b) 136,120,105,91,78,66...  
    (the total number of different possible 2 card hands that include two
    10 valued cards when there are zero, one, two, etc... of the 10
    valued cards removed from the deck)


(17-n)*(16-n)/2


(c) 5,10,20,40,80,160 (The maximum amount of money you can lose
    playing the martingale "double-your-bet-when-you-lose" strategy
    for one, two, three etc... hands)



5 * 2^x


 Suppose g: A --> A, and f: A --> A are both one to one functions
from a set to itself.  Prove that the composition of f and g is also a
one to one function.  That is, prove (f o g): A --> A is one to one.

We need to prove:

forall x,y in set A,
  (x ~= y) --> (f o g)(x) ~= (f o g)(y)

  To prove the implication, we assume x ~= y, then prove f(x) ~= f(y)

  Assume, x ~= y
    then g(x) ~= g(y),           (because g is one to one).
    then f(g(x)) ~= f(g(y))      (because f is one to one, and g(x)~=g(y)).
    so (f o g)(x) ~= (f o g)(y)  (f o g)(x) = f(g(x))


 if f is a one to one function and f o g is a one to one function,
     must g also be a one to one function?

  To be concrete, let us define domains and co-domains for the functions:
   f: B --> C
   g: A --> B

We will use an indirect proof (which is to say, we prove the
contrapositive, that if g is not a one-to-one function, then (f o g)
is not a one to one function)

Assume g is not a one to one function.

 Then there exists some different values x,y such that g(x) = g(y)
 then f( g(x) ) = f( g(y) )  (because g(x), g(y) are equal),

  therefore (f o g) is not one-to-one.

so, by indirect proof, if f o g is one to one, then g is one to one.




let f: R⁺ ----> R be defined by f(x) = log(x).  Prove
that f is 1-1.  (R⁺ is the set of real numbers > 0).

Suppose f(x) = f(y)
 by defn. of f, we have:
  log(x) = log(y)
  2^log(x) = 2^log(y)
  x = y

so f(x) = f(y) -> x = y, so f is 1-1.



 Let A be the set {4,5,6}, and B be the set {1,2,3,4,5}.  Let
P(A) be the "powerset" of A, and P(B) be the powerset of B.

How many elements does the set A x B have?

15


How many elements does A x P(A) have? 

3 * 2³.


list two different elements of A x P(A).

(5,{}),  (4,{4,5}).  (many correct answers).


How many elements does P(A) x P(B) have?

2³ *2⁵