4 (Numbers and Sets)

Solution

(k n)

to be the number of

k

-element subsets of an

n

-element set. Equivalently, count ordered selections and divide by the

k!

orders of each subset to obtain

(k n) = n! / [k! (n - k)!]

, with

(0 n) = (n n) = 1

Fix one distinguished element. The

k

-subsets not containing it are counted by

(k n - 1)

; those containing it correspond bijectively to

(k - 1)

-subsets of the remaining

n - 1

elements. These are disjoint and exhaustive classes, proving Pascal's identity:

(k n - 1) + (k - 1 n - 1) = (k n) .

k

, retaining an arbitrary fixed

n \geq 0

. At

k = 0

, both sides equal one. Suppose

\sum_{j = 0}^{k} (j n + j) = (k n + k + 1)

. Adding the next term and applying Pascal's identity gives

\sum_{j = 0}^{k + 1} (j n + j) = (k n + k + 1) + (k + 1 n + k + 1) = (k + 1 n + k + 2) .

This is the required statement for

k + 1

, completing the induction, including

n = 0

. Hence the hockey-stick identity in this form is

j = 0 \sum k (j n + j) = (k n + k + 1) (n, k \geq 0) .

There are no discussions about this article yet.

There are currently no matching articles.