1. Please prove the following using induction.

n choose 0 = n choose n = 1 for all n greater or equal to 0

n choose k = n - 1 choose k - 1 plus n - 1 choose k for all 0 < k < n; n greater than or equal to 0

2. Please prove using the Inclusion and Exclusion Principle.

Patrons of a local bookstore can sign up for advance notification of new book arrivals in genres of interest. In the first month of this service, 32 sign up for mysteries, 34 for spy novels, 18 for westerns, and 41 for science fiction. Of these, 17 sign for both mysteries and spy novels, 8 for both mysteries and westerns, 19 for mysteries and science fiction, 5 for spy novels and westerns, 20 for spy novels and science fiction, and 12 for westerns and science fiction. In addition, 2 sign up for mysteries, spy novels and westerns; 11 for mysteries, spy novels, and science fiction; 6 for mysteries, westerns, and science fiction; and 5 for spy novels, westerns, and science fiction. Finally, 2 people sign up for all four categories. How many people signed up for service in the first month?

3. Prove using Pascal's formula.

C(n + 2, r) = C(n,r) + 2C(n, r - 1) + C(n, r - 2) for all 2 less than or equal to r which is less than or equal to n

4. a) Expand (1 + x)^n

b) Differentiate both sides of the equation from part (a) with respect to x to obtain:

n(1 + x)^n-1 = C(n, 1) + 2C(n, 2)x + 3C(n, 3)x^2 + ... + nC(n, n)x^n-1

c) Prove that C(n, 1) + 2C(n, 2) + 3C(n, 3) + ... + nC(n,n) = n2^n-1

d) Prove that C(n, 1) - 2C(n,2) + 3C(n, 3) - 4C(n, 4) + ... + (-1)^n-1 ? nC(n, n) = 0

5. a) Prove that (2^n + 1) / (n + 1) = C(n,0) + (1/2)C(n,1) + (1/3)C(n,2) + ... +

(1/n+1)C(n,n)

b) Prove that (1/n + 1) = C(n,0) + (1/2)C(n,1) + (1/3)C(n,2) + ... + (-1)^n ? (1/n + 1)C(n,n)