Home Work 1

Induction

1. Prove that Sum(i=0 through N) 2^i = 2^(N+1) -1

2. Prove that number of edges in a connected tree is (n-1)

3. Prove that Sum(i=0 through N) i^2 = N(N+1)(2N+1)/6

For the following relations between sets A and B mention 
if they are partial function, total function, one to one 
and/or onto:

A={a, b, c} B={1, 2}

4. {(a, 1), (b, 1), (c, 1)}

5. {(a, 2), (b, 2)}

6. {(a, 1), (a, 2)}