such strings (choosing where to put the 1™s).

There are m

2.5.2 Some more identities

Proposition.

n n

= n ∈ N0 , k ∈ Z

k n’k

Proof. For: choosing a k-subset is the same as choosing an n ’ k-subset to reject.

Proposition.

n n’1 n’1

= + n ∈ N0 , k ∈ Z

k k’1 k

Proof. This is trivial if n < 0 or k ¤ 0, so assume n ≥ 0 and k > 0. Choose a special

element in the n-set. Any k-subset will either contain this special element (there are

n’1 n’1

k’1 such) or not contain it (there are such).

k

2.5. SELECTION AND BINOMIAL COEFFICIENTS 15

In fact

Proposition.

x x’1 x’1

= + k∈Z

k k’1 k

Proof. Trivial if k < 0, so let k ≥ 0. Both sides are polynomials of degree k and are

equal on all elements of N0 and so are equal as polynomials as a consequence of the

Fundamental Theorem of Algebra. This is the “polynomial argument”.

This can also be proved from the de¬nition, if you want to.

Proposition.

x m x x’k

= m, k ∈ Z.

m k k m’k

Proof. If k < 0 or m < k then both sides are zero. Assume m ≥ k ≥ 0. Assume

x = n ∈ N (the general case follows by the polynomial argument). This is “choosing

a k-subset contained in an m-subset of a n-set”.

Proposition.

x x x’1

= k ∈ Z \ {0}

k k k’1

Proof. We may assume x = n ∈ N and k > 0. This is “choosing a k-team and its

captain”.

Proposition.

n

n+1 k

= , m, n ∈ N0

m+1 m

k=0

Proof. For

n+1 n n n n’1 n’1

= + = + +

m+1 m m+1 m m m+1

and so on.

n 1

A consequence of this is that k=1 k m = m+1 (n + 1)m+1 , which is obtained by

n

multiplying the previous result by m!. This can be used to sum k=1 k m .

Proposition.

r+s r s

= r, s, m, n ∈ Z

m+n m+k n’k

k

Proof. We can replace n by m + n and k by m + k and so we may assume that m = 0.

So we have to prove:

r+s r s

= r, s, n ∈ Z.

n k n’k

k

Take an (r + s)-set and split it into an r-set and an s-set. Choosing an n-subset

amounts to choosing a k-subset from the r-set and an (n ’ k)-subset from the s-set for

various k.

CHAPTER 2. INDUCTION AND COUNTING

16

2.6 Special Sequences of Integers

2.6.1 Stirling numbers of the second kind

De¬nition. The Stirling number of the second kind, S(n, k), n, k ∈ N0 is de¬ned

as the number of partitions of {1, . . . , n} into exactly k non-empty subsets. Also

S(n, 0) = 0 if n > 0 and 1 if n = 0.

n

Note that S(n, k) = 0 if k > n, S(n, n) = 1 for all n, S(n, n ’ 1) = and

2

S(n, 2) = 2n’1 ’ 1.

Lemma 2.1. A recurrence: S(n, k) = S(n ’ 1, k ’ 1) + kS(n ’ 1, k).

Proof. In any partition of {1, . . . , n}, the element n is either in a part on its own (S(n’

1, k ’ 1) such) or with other things (kS(n ’ 1, k) such).

Proposition. For n ∈ N0 , xn = S(n, k)xk .

k

Proof. Proof is by induction on n. It is clearly true when n = 0, so take n > 0 and

assume the result is true for n ’ 1. Then

xn = xxn’1

S(n ’ 1, k)xk

=x

k

S(n ’ 1, k)xk (x ’ k + k)

=

k

S(n ’ 1, k)xk+1 + kS(n ’ 1, k)xk

=

k k

S(n ’ 1, k ’ 1)xk + kS(n ’ 1, k)xk

=

k k

S(n, k)xk as required.

=

k

2.6.2 Generating Functions

Recall the Fibonacci numbers, Fn such that F1 = F2 = 1 and Fn+2 = Fn+1 + Fn .

Suppose that we wish to obtain a closed formula.

First method

√

1± 5

n 2

Try a solution of the form Fn = ± . Then we get ± ’ ± ’ 1 = 0 and ± = 2. We

then take

√n √n

1+ 5 1’ 5

Fn = A +B

2 2

and use the initial conditions to determine A and B. It turns out that

√n √n

1 1+ 5 1’ 5

Fn = √ ’ .

2 2

5

2.6. SPECIAL SEQUENCES OF INTEGERS 17

√ √

1+ 5 1’ 5

> 1 and < 1 so the solution grows exponentially. A shorter

Note that 2 2

√ n

1+ 5