in order of size on rod A. The challenge is to move the rings from A to B so that a

larger ring is never placed on top of a smaller one.

We write the number of moves required to move n rings as Tn and claim that

Tn = 2n ’ 1 for n ∈ N0 . We note that T0 = 0 = 20 ’ 1, so the result is true for n = 0.

We take k > 0 and suppose we have k rings. Now the only way to move the largest

ring is to move the other k ’ 1 rings onto C (in Tk’1 moves). We then put the largest

ring on rod B (in 1 move) and move the k ’ 1 smaller rings on top of it (in Tk’1 moves

again). Assume that Tk’1 = 2k’1 ’ 1. Then Tk = 2Tk’1 + 1 = 2k ’ 1. Hence the

result is proven by the principle of induction.

2.3 Strong Principle of Mathematical Induction

Proposition (Strong Principle of Induction). If P (n) is a statement about n for each

n ∈ N0 , P (k0 ) is true for some k0 ∈ N0 and the truth of P (k) is implied by the truth

of P (k0 ), P (k0 + 1), . . . , P (k ’ 1) then P (n) is true for all n ∈ N0 such that n ≥ k0 .

The proof is more or less as before.

Example (Evolutionary Trees). Every organism can mutate and produce 2 new ver-

sions. Then n mutations are required to produce n + 1 end products.

Proof. Let P (n) be the statement “n mutations are required to produce n + 1 end

products”. P0 is clear. Consider a tree with k + 1 end products. The ¬rst mutation (the

root) produces 2 trees, say with k1 + 1 and k2 + 1 end products with k1 , k2 < k. Then

k + 1 = k1 + 1 + k2 + 1 so k = k1 + k2 + 1. If both P (k1 ) and P (k2 ) are true then

there are k1 mutations on the left and k2 on the right. So in total we have k1 + k2 + 1

mutations in our tree and P (k) is true is P (k1 ) and P (k2 ) are true. Hence P (n) is true

for all n ∈ N0 .

2.4 Recursive De¬nitions

(Or in other words) De¬ning f (n), a formula or functions, for all n ∈ N0 with n ≥ k0

by de¬ning f (k0 ) and then de¬ning for k > k0 , f (k) in terms of f (k0 ), f (k0 + 1),

. . . , f (k ’ 1).

The obvious example is factorials, which can be de¬ned by n! = n(n ’ 1)! for

n ≥ 1 and 0! = 1.

Proposition. The number of ways to order a set of n points is n! for all n ∈ N0 .

Proof. This is true for n = 0. So, to order an n-set, choose the 1st element in n ways

and then order the remaining n ’ 1-set in (n ’ 1)! ways.

Another example is the Ackermann function, which appears on example sheet 2.

2.5. SELECTION AND BINOMIAL COEFFICIENTS 13

2.5 Selection and Binomial Coef¬cients

We de¬ne a set of polynomials for m ∈ N0 as

xm = x(x ’ 1)(x ’ 2) . . . (x ’ m + 1),

which is pronounced “x to the m falling”. We can do this recursively by x0 = 1 and

xm = (x ’ m + 1)xm’1 for m > 0. We also de¬ne “x to the m rising” by

xm = x(x + 1)(x + 2) . . . (x + m ’ 1).

x

(read “x choose m”) by

We further de¬ne m

xm

x

= .

m m!

x

It is also convienient to extend this de¬nition to negative m by = 0 if m < 0,

m

m ∈ Z. By ¬ddling a little, we can see that for n ∈ N, n ≥ m

n n!

= .

m m!(n ’ m)!

n

Proposition. The number of k-subsets of a given n-set is .

k

Proof. We can choose the ¬rst element to be included in our k-subset in n ways, then

then next in n ’ 1 ways, down to the k th which can be chosen in n ’ k + 1 ways.

k

However, ordering of the k-subset is not important (at the moment), so divide n to get

k!

the answer.

Theorem 2.1 (The Binomial Theorem). For a and b ∈ R, n ∈ N0 then

n k n’k

n

(a + b) = ab .

k

k

There are many proofs of this fact. We give one and outline a second.

Proof. (a + b)n = (a + b)(a + b) . . . (a + b), so the coef¬cient of ak bn’k is the number

of k-subsets of an n-set ” so the coef¬cient is n . k

Proof. This can also be done by induction on n, using the fact that

n n’1 n’1

= + .

k k’1 k

There are a few conseqences of the binomial expansion.

n

1. For m, n ∈ N0 and n ≥ m, ∈ N0 so m! divides the product of any m

m

consecutive integers.

2. Putting a = b = 1 in the binomial theorem gives 2n = k n ” so the number

k

of subsets of an n-set is 2n . There are many proofs of this fact. An easy one is

by induction on n. Write Sn for the total number of subsets of an n-set. Then

S0 = 1 and for n > 0, Sn = 2Sn’1 . (Pick a point in the n-set and observe that

there are Sn’1 subsets not containing it and Sn’1 subsets containing it.

CHAPTER 2. INDUCTION AND COUNTING

14

3. (1 ’ 1)n = 0 = k n (’1)k ” so in any ¬nite set the number of subsets of

k

even sizes equals the number of subsets of odd sizes.

It also gives us another proof of Fermat™s Little Theorem: if p is prime then ap ≡ a

(mod p) for all a ∈ N0 .

Proof. It is done by induction on a. It is obviously true when a = 0, so take a > 0 and

assume the theorem is true for a ’ 1. Then

p

ap = ((a ’ 1) + 1)

p

p

≡ (a ’ 1) + 1 mod p as ≡0 (mod p) unless k = 0 or k = p

k

≡ a ’ 1 + 1 mod p

≡ a mod p

2.5.1 Selections

The number of ways of choosing m objects out of n objects is

ordered unordered

n

nm

no repeats m

n’m+1

nm

repeats m

The only entry that needs justi¬cation is n’m+1 . But there is a one-to-one cor-

m

respondance betwen the set of ways of choosing m out of n unordered with possible

repeats and the set of all binary strings of length n + m ’ 1 with m zeros and n ’ 1

ones. For suppose there are mi occurences of element i, mi ≥ 0. Then

n

mi = m ” 0 . . . 0 1 0 . . . 0 1 . . . 1 0 . . . 0 .

i=1 m1 m2 mn