Consider the following different definitions:
= the number of subsets of size k that can be made
from an n-element set.
Pascal(n, k) = the entries of Pascals
triangle which follow these two rules:
Pascal(n, k) = Pascal(n
1, k 1) + Pascal(n
1, k)
Pascal(n, 0) = Pascal(n,
n) = 1.
a) Write out the first few values of in a triangle:
b) Write out the first few values of f(n,
k) in a triangle:
c) Write out the first few values of a Pascal(n,
k) triangle.
d) Show that for any positive integer n and for ,
f(n, k) = Pascal(n,
k). Hint: you can do this by showing that f(n,
k) obeys the same rules that define Pascal(n,
k).
e) Show that for any positive integer n and for ,
= Pascal(n, k).
Because of problems 5d and 5e, we can use the same symbol for
,
f(n, k), and Pascal(n,
k). By convention, most people use .