EF Properties

🔗
The values are symmetric about a vertical line through the centre of the triangle.
🔗
It appears that every entry is the sum of the two entries immediately above.
🔗
It appears that each row sums to a power of $2 .$

🔗

We have already observed the first pattern as arising from the equivalence of choosing versus rejecting elements to form a subset (see Corollary 22.2.4 and Remark 22.2.5).

🔗

The next two propositions confirm that the other two observed patterns continue throughout the triangle.

🔗

Proposition 22.4.2.

🔗

For

n \geq 2

and

1 \leq k \leq n - 1,

we have

C_{k}^{n} = C_{k - 1}^{n - 1} + C_{k}^{n - 1} .

🔗

Proof.

We could prove this equality just by comparing the factorial formulas involved on the left-hand and right-hand sides. But instead we will consider each of these combination values as representing the number of subsets of a certain size.

Write

A = N_{< n} = {0, 1, 2, \dots, n - 1}

so that

| A | = n .

Then the left-hand side of the equality in the statement of the proposition represents the number of subsets of

A

of size

k .

Let’s break that collection of subsets into two subcollections.

Subsets of $A$ of size $k$ that contain $0$ .

Each of these subsets will consist of

0

along with

k - 1

nonzero elements. As

A

contains

n - 1

nonzero elements from which to choose, there are

C_{k - 1}^{n - 1}

ways to select those additional subset elements from

A .

Subsets of $A$ of size $k$ that do not contain $0$ .

Each of these subsets must consist of

k

nonzero elements. As

A

contains

n - 1

nonzero elements from which to choose, there are

C_{k}^{n - 1}

ways to select those subset elements from

A .

Adding these two disjoint cases together using the Addition Rule yields the right-hand side of the equality.

🔗

Proposition 22.4.3.

🔗

For

n \geq 0,

we have

\sum_{k = 0}^{n} C_{k}^{n} = 2^{n} .

🔗

Proof.

First, recall that the notation on the left-hand side is summation notation:

\sum_{k = 0}^{n} C_{k}^{n} = C_{0}^{n} + C_{1}^{n} + \dots + C_{n}^{n} .

Let

A = N_{< n},

so that

| A | = n .

Then

| P (A) | = 2^{n}

(Theorem 12.2.9). So the right-hand side of the equality represents the number of possible subsets of

A .

On the other hand, for each index

k

in the sum on the left-hand side, the term

C_{k}^{n}

is the number of subsets of

A

of size

k .

Using the Addition Rule, the sum of these terms must also be the total number of possible subsets of

A .

🔗

Here is one further property of the choose function.

🔗

Proposition 22.4.4.

🔗

For

0 \leq m \leq n,

we have

C_{m + 1}^{n + 1} = \sum_{k = m}^{n} C_{m}^{k} .

🔗

Proof.

Suppose

A

is a finite set with

| A | = n + 1 .

(For example, we could use

A = N_{< n + 1},

but that might get confusing between numbers as elements of

A

and numbers as cardinalities of subsets of

A .

) Then the left-hand side of the equality is the number of subsets of

A

of size

m + 1 .

Here is a systematic way we could create that those subsets.

Choose an ordering of the elements of

A,

so that

A = {a_{1}, a_{2}, \dots, a_{n + 1}},

though we will not count this choice of ordering. Then, proceed as follows.

Write

$B_{1} = {a_{1}, a_{2}, \dots, a_{m + 1}},$

so that $B_{1} \subseteq A$ with $| B_{1} | = m + 1 .$ Then there is exactly $1 = C_{m + 1}^{m + 1}$ subset of $B_{1}$ of size $m + 1,$ which is $B_{1}$ itself. And this subset of $B_{1}$ is also a subset of $A .$
Write

$B_{2} = {a_{1}, a_{2}, \dots, a_{m + 1}, a_{m + 2}},$

so that $B_{1} \subseteq B_{2} \subseteq A$ with $| B_{2} | = m + 2 .$ Using only the elements of $B_{2},$ to create a new subset $X \subseteq A$ of size $m + 1$ that we have not already counted we must include the new element $a_{m + 2},$ with the remaining $m$ elements to make up $X$ chosen from $B_{1} .$ So we get $C_{m}^{m + 1}$ new subsets of $A$ of size $m + 1$ from $B_{2} .$
Write

$B_{3} = {a_{1}, a_{2}, \dots, a_{m + 1}, a_{m + 2}, a_{m + 3}},$

so that $B_{2} \subseteq B_{3} \subseteq A$ with $| B_{3} | = m + 3 .$ Using only the elements of $B_{3},$ to create a new subset of $X \subseteq A$ of size $m + 1$ that we have not already counted we must include the new element $a_{m + 3},$ with the remaining $m$ elements to make up $X$ chosen from $B_{2} .$ So we get $C_{m}^{m + 2}$ new subsets of $A$ of size $m + 1$ from $B_{3} .$

And so on. The last step in this process is when we create new subsets of size

m + 1

by first choosing to include

a_{n + 1},

and then choosing the remaining

m

elements from

A ∖ {a_{n + 1}},

giving us

C_{m}^{n}

new subsets.

Every subset

X \subseteq A

of size

m + 1

is accounted for in the above process, since every such subset must contain at least one element with index

m + 1

or larger. If

a_{N}

is the element in

X

with the largest index, then

X

is one of the subsets considered in step

ℓ,

where

N = m + ℓ .

So adding up each of these disjoint cases using the Addition Rule must yield the total number of subsets of

A

of size

m + 1 .

Replacing the

C_{m + 1}^{m + 1}

total from the first step with

C_{m}^{m}

(since both are equal to

1

) to match the pattern of the subsequent steps, we obtain

C_{m + 1}^{n + 1} = C_{m}^{m} + C_{m}^{m + 1} + \dots + C_{m}^{n},

as desired.

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 22.4 Properties

Proposition 22.4.2.

Proof.

Subsets of $A$ of size $k$ that contain $0$ .

Subsets of $A$ of size $k$ that do not contain $0$ .

Proposition 22.4.3.

Proof.

Proposition 22.4.4.

Proof.

Section 22.4 Properties

Proposition 22.4.2.

Proof.

Subsets of A of size k that contain 0.

Subsets of A of size k that do not contain 0.

Proposition 22.4.3.

Proof.

Proposition 22.4.4.

Proof.

Subsets of $A$ of size $k$ that contain $0$ .

Subsets of $A$ of size $k$ that do not contain $0$ .