Summer Mathematics Homepage

Foundations of Mathematics
Summer Program for High School Students
Columbia University -- July 2001 -- Blumberg
Homework Set #2 -- Selected answers

1. (1 point) a. For n > 3, n! > 2^n. After showing this true for n = 4 (4! > 2^4), we want to show that if n! > 2^n, then (n+1)! > 2^(n+1). Recognizing that (n+1)! = (n+1)(n!) and that 2^(n+1) = 2 * 2^n, we can rewrite the "then" statement as (n+1)(n!) > 2 * 2^n. Since we already accept that n! > 2^n, we substitute n! for 2^n on the right side of the "then" statement and realize that if we can prove this new form of the statement, then the original form will obviously be true as well (i.e. if anything we've just made the right side larger, so if we can prove that it is still smaller than the left side the original statement will be true as well). Dividing both sides, then, by n! we get (n+1) > 2, which is clearly true given the initial condition of the proof (n>3), so the induction step is done, and we know that for n > 3, n! > 2^n.

b. Here the induction step involves showing that if 1(2) + 2(3) + ... + n(n+1) = [n(n+1)(n+2)]/3, then 1(2) + 2(3) + ... + n(n+1) + (n+1)(n+2) = [(n+1)(n+2)(n+3)]/3. Using elementary algebra it is possible to show that the difference between both the left sides and right sides of the equations is (n+1)(n+2), and thus prove the induction step.

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

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

4. (2 points) Prove the following equality directly, and then by mathematical induction: n^2 = C(n,2) + C(n+1,2)

5. In the following diagram, a) 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)? What is the probability that a non-descending path from (0,0) to (7,5) passes through the point (4,3)?

6. (Extra Credit: 2 points) You'll notice that the sum given in the problem can be found on either of two diagonals in the Triangle, and thus we can write the numbers in either of two ways:

C(3,0) + C(4,1) + C(5,2) + C(6,3) + C(7,4) + C(8,5) = C(9,5)
C(3,3) + C(4,3) + C(5,3) + C(6,3) + C(7,3) + C(8,3) = C(9,4)

Noting that these diagonal patterns appear throughout the triangle, we can generalize and write a variety of equations that might be proven directly or by mathematical induction. Two examples, derived from the examples just mentioned, would be:

C(n,0) + C(n+1, 1) + C(n+2, 2) + ..... + C(n+r, r) = C(n+r+1, r)
C(n,r) + C(n+1, r) + C(n+2, r) + ..... + C(n+r, r) = C(n+r+1, r+1)

Summer Mathematics Homepage Summer Mathetmatics Reference Page
© 2001 Roger B. Blumberg