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.
Previous Page Next Page