14 1. The Real Numbers

Induction step: If we assume the formula is true for a certain n, then multiplying

both sides of this formula by x + y yields

(x +

y)n+1

= x

n

k=0

n

k

xkyn−k

+ y

n

k=0

n

k

xkyn−k

=

n

k=0

n

k

xk+1yn−k

+

n

k=0

n

k

xkyn−k+1.

(1.2.7)

If we change variables in the first sum on the second line of (1.2.7) by replacing k

by k − 1, then our expression for (x +

y)n+1

becomes

xn+1

+

n

k=1

n

k − 1

xkyn−k+1

+

n

k=1

n

k

xkyn−k+1

+

yn+1

=

xn+1

+

n

k=1

n

k − 1

+

n

k

xkyn+1−k

+

yn+1.

(1.2.8)

If we use the identity (to be proved in Exercise 1.2.17)

n

k − 1

+

n

k

=

n + 1

k

,

then the right side of equation (1.2.8) becomes

xn+1

+

n

k=1

n + 1

k

xkyn+1−k

+

yn+1

=

n+1

k=0

n + 1

k

xkyn+1−k.

Thus, the binomial formula is true for n + 1 if it is true for n. This completes the

induction step and the proof of the theorem.

Exercise Set 1.2

In the first seven exercises use only Peano’s axioms and results that were proved in

Section 1.2 using only Peano’s axioms.

1. Prove that the commutative law for addition, n + m = m + n, holds in N. Use

induction and Examples 1.2.6 and 1.2.5.

2. Prove that if n, m ∈ N, then m + n = n. Hint: Use induction on n.

3. Use the preceding exercise to prove that if n, m ∈ N, n ≤ m, and m ≤ n, then

n = m. This is the reflexive property of an order relation.

4. Prove that the order relation on N has the transitive property: if k ≤ n and

n ≤ m, then k ≤ m.

5. Use the preceding exercise and Peano’s axioms to prove that if n ∈ N, then for

each element m ∈ N either m ≤ n or n ≤ m. Hint: Use induction on n.

6. Show how to define the product nm of two natural numbers. Hint: Use induc-

tion on m.

7. Use the definition of product that you gave in the preceding exercise to prove

that if n, m ∈ N, then n ≤ nm.