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?

a) (1 point) C(7,3)

b) (1 point) The answer can be found by taking successive combinations: C(9,2), C(7,3) and C(4,4) and multiplying them to find the total number of combinations; or, we can apply the multinomial formula, C(9,2,3,4), which also yields 9!/(2!*3!*4!).

c) (1 point) C(12,2)*C(10,3)*C(7,4) or, if you realize how a bionomial coefficient can be turned into a multinomial coefficient , C(12,2,3,4,3). Either way the answer is 12!/(2!*3!*4!*3!)

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?

a) (1 point) We divide the number of permutations of 10 distinct elements, by the number of permutations in each equivalence class (created by the repeated letters) to get: 10!/(2!*2!*3!).

b) (1 point) This part is a bit trickier, because not every combination in C(10,3) will be duplicated the same number of times. For example, the combination BOR will be counted twice in C(10,3), but the combination BPR will be counted only once, and the combination OKE will be counted 12 times! So what can we do? We can either calculate C(10,3) and subtract the number of duplicate combinations, or, realizing that there are actually 6 different letters in the word, we can calculate C(6,3) and then add the combinations we've left out (i.e. those containing 2 Os, those containing 2 Ks, and those containing 2 or 3 Es). It seems to me that, in this case anyway, the latter approach is easier, and we get C(6,3) + 5 + 5 + 6 = 36.

First we do the direct proof, in which we expand the right side of the equation and show that it is equal to n^2. The tricky part is to figure out how to get common denominators, but once you realize that n! = n * (n-1)! = n*(n-1)*(n-2)!, etc., the algebra is easy. Then, we move on to the proof by induction:

I. Let n=2 (since when n=1, the term C(n,2) makes no sense). Then the statement says: 2^2 = C(2,2) + C(3,2) = 1 + 3 = 4.

II. We want to show that:

• if n^2 = C(n,2) + C(n+1,2)
• then (n+1)^2 = C(n+1, 2) + C(n+2, 2)

To do this, it will be sufficient to show that the difference between the left sides of the two equations is equal to the right sides of the two equations. In other words, we want to show that:

(n+1)^2 - n^2 = C(n+1,2) + C(n+2,2) - (C(n,2) + C(n+1,2))

Expanding the left side and canceling terms on both sides we get:

2n+1 = C(n+2,2) - C(n,2) = (n+2)!/(n!*2!) - [ n!/((n-2)!*2!)]

In order to further reduce the right side of the equation we could a) expand, reduce and/or find common denominators for the two fractions, and subtract them; or b) rewrite the first term so that it can be compared to a combination of n elements taken 2 at a time.

a) Since n! = n*(n-1)*(n-2)!, we can multiply both the numerator and the denominator of the second term by n(n-1) to get common denominators of n!*2!. And since (n+2)! = (n+2)*(n+1)*n!, we can rewrite the numerator of the first term in a way that will allow for later simplifications. We get:

(n+2)*(n+1)*n!/(n!*2!) - [ n(n-1)*n!/(n!*2!)]

Clearly the n! can be canceled in both terms, leaving us with:

(n+2)*(n+1)/2! - [ n(n-1)/2!] = (n^2 + 2n + 1)/2 - [(n^2 - n)/2]

which of course reduces to 2n+1.

b) Recalling that C(n,r) = C(n-1,r) + C(n-1, r-1) from the discussion of Pascal's Triangle (see Notes from Week #3), we can rewrite the right side of the equation (C(n+2,2) - C(n,2)) as:

(C(n+1,2) + C(n+1,1)) - C(n,2) = C(n,2) + C(n,1) + C(n,1) + C(n,0) - C(n,2)

Since we know that C(n,0) = 1, and C(n,1) = n, this expression just becomes: n + n + 1 = 2n+1.

Of course an alternative, and perhaps much easier, way to prove the induction step is to show, by expanding and simplifying both sides, that the "then" statement is always true (regardless of the "if" assumption).

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)?

a) (1 point) Like the 2-D graph problem we considered when we first discussed the interpretations of C(n,r), we see that the question asks how many ways can we make 12 moves, such that exactly 7 are along the x axis, and exactly 5 are along the y axis. Therefore the answer is C(12,7) or C(12,5).

b) (1 point) Clearly there will be fewer ways to reach (7,5) if you are required to pass through any particular point. Since there are C(7,4) ways to get from (0,0) to (4,3) and C(5,3) ways to go from (4,3) to (7,5), the answer is: C(7,4) * C(5,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:

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: