38.6. EXERCISES 777

There is one way to fill the front right seat with Eliphaz. Then there are 10 favorableways to fill the seat on the left side of Eliphaz with someone other than Eliphaz. Thereare now 10 students left who can fill the remaining seats in any order because you haveused two. Thus there are 1× 10× 10× 9 ways to have a favorable outcome. There are12×11×10×9 ways for them to select seats at random. Therefore, the probability is

1×10×10×912×11×10×9

=5

66

38.6 Exercises1. Let k≤ n where k and n are natural numbers. P(n,k) , permutations of n things taken

k at a time, is defined to be the number of different ways to form an ordered list of kof the numbers {1,2, · · · ,n} . Show

P(n,k) =n!

(n− k)!.

2. Now consider the word “mississippi”. By rearranging the letters, how many dis-tinctly different words can you obtain? Note that for each list of these letters the fourdifferent s are indistinguishable. There are therefore, 4! ways which are not reallydifferent.

3. Using Problem 1, show the number of ways of selecting a set of k things from a setof n things is n!

(n−k)!k! .

4. Prove by induction that n < 2n for all natural numbers n≥ 1.

5. Prove by the binomial theorem and Problem 3 that the number of subsets of a givenfinite set containing n elements is 2n.

6. Show that for p ∈ (0,1) , ∑nk=0(n

k

)kpk (1− p)n−k = np.

7. Using the binomial theorem prove that for all n ∈ N,(1+

1n

)n

≤(

1+1

n+1

)n+1

.

Hint: Show first that(n

k

)= n·(n−1)···(n−k+1)

k! . By the binomial theorem,

(1+

1n

)n

=n

∑k=0

(nk

)(1n

)k

=n

∑k=0

k factors︷ ︸︸ ︷n · (n−1) · · ·(n− k+1)

k!nk .

Now consider the term n·(n−1)···(n−k+1)k!nk and note that a similar term occurs in the

binomial expansion for(1+ 1

n+1

)n+1except that n is replaced with n+ 1 wherever

this occurs. Argue the term got bigger and then note that in the binomial expansionfor(1+ 1

n+1

)n+1, there are more terms.