Foundations of Mathematics
Summer Program for High School Students
Columbia University -- July 2001 -- Blumberg
Homework Set #2 -- Due: Friday, July 20th (by noon)
1) Prove one (1) of the following by mathematical induction:
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 equality directly, and then again 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 of numbers along a diagonal holds, and then try to formalize this pattern in the form of an equation that could be proved by induction. (Hint: every term in the Triangle can be expressed in combinatorial form.)
