1.2. The Natural Numbers 15

For the remaining exercises you are no longer restricted to just using Peano’s axioms

and their immediate consequences.

8. Using induction, prove that

7n − 2n is divisible by 5 for every n ∈ N.

9. Using induction, prove that

n

k=1

k =

n(n + 1)

2

for every n ∈ N.

10. Using induction, prove that

n

k=1

(2k − 1) =

n2

for every n ∈ N.

11. Finish the prove of Theorem 1.2.3 by showing that there is only one sequence

{xn} which satisfies the conditions of the theorem.

12. If x1 is chosen so that 0 x1 2 and xn is defined inductively by xn+1 =

√

xn + 2, then prove by induction that 0 xn ≤ xn+1 2 for all n ∈ N.

13. Let a sequence {xn} of numbers be defined recursively by

x1 = 0 and xn+1 =

xn + 1

2

.

Prove by induction that xn ≤ xn+1 for all n ∈ N. Would this conclusion change

if we set x1 = 2?

14. Let a sequence {xn} of numbers be defined recursively by

x1 = 1 and xn+1 =

1

1 + xn

.

Prove by induction that xn+2 is between xn and xn+1 for each n ∈ N.

15. Mathematical induction also works for a sequence Pk,Pk+1,... of propositions,

indexed by the integers n ≥ k for some k ∈ N. The statement is: if Pk is true

and Pn+1 is true whenever Pn is true and n ≥ k, then Pn is true for all n ≥ k.

Prove this.

16. Use induction in the form stated in the preceding exercise to prove that

n2 2n

for all n ≥ 5.

17. Prove the identity

n

k − 1

+

n

k

=

n + 1

k

,

which was used in the proof of Theorem 1.2.12.

18. Write out the binomial formula in the case n = 4.

19. Prove the well ordering principal for the natural numbers: each non-empty

subset S of N contains a smallest element. Hint: Apply the induction axiom to

the set

T = {n ∈ N : n m for all m ∈ S}.

20. Use the result of Exercise 1.2.19 to prove the division algorithm: if n and m

are natural numbers with m n and if m does not divide n, then there are

natural numbers q and r such that n = qm + r and r m. Hint: Consider the

set S of all natural numbers s such that (s + 1)m n.