Foundations of Mathematics
Summer Program for High School Students
Columbia University -- July 1999 -- Blumberg
Homework Set #2 -- Due: July 23rd by noon.

1) Prove the following by mathematical induction:

a). For n > 3, n! > 2^n.

b). 1(2) + 2(3) + 3(4) + .... + n(n+1) = [n(n+1)(n+2)]/3

2) How many ways are there to choose a committee of 3 persons from a population of 7 persons? How many ways are there to choose committees of 2,3, and 4 persons from a population of 9 persons? from a population of 12 persons?

3) How many ways are there to arrange the letters in BOOKKEEPER in a row? How many ways are there to choose 3 letters from BOOKKEEPER?

4) Prove the following by mathematical induction:

5. a) In the following diagram, how many different ways are there from the origin (0,0) to the point (7,5), if you are allowed to move only up or to the right (i.e. non-descending paths)? How will your answer change if your path is required to pass through (4,3) on the way to (7,5)?

6) Locate the following sum in Pascal's Triangle:

Give other instances in the Triangle where the same pattern for finding the sum holds, and try to formalize this pattern in the form of an equation that could be proved by induction.