66 CHAPTER 1 Sets, Proof Templates, and Induction
- Refer to the Square Root II algorithm.
(a) Finish the proof of Theorem 5.
(b) Show that En+l = --^2 ,/(2R,). (Hint: Simplify VT1 - (Rn + (17/Rn))/2.)
(c) How close do you think the value printed is to the actual value of VP-7? Approxi-
mately how many decimal digits in accuracy is that? - Challenge: Exactly where is the mistake in the following proof that all personal com-
puters are the same brand? Let T = {n E N : n > 1 and in every set of n personal
computers, all the personal computers are the same brand). Prove by induction that for
every natural number n such that n > 1 is in T.
(Base step) 1 E T, since, trivially, if a set of personal computers contains only one
computer, then every (one) computer in the set has the same brand.
(Inductive step) Suppose n E T. We need to show n + I E T. So, let P be any set
of n + 1 personal computers. Pick any computer c e P; we need to show that every
computer in P is the same brand as c. So, let d be any computer in P. If d = c,
then, trivially, d and c are the same brand. Otherwise, c E P - {d}. The set P - {d}
contains n computers, so by inductive hypothesis, all the computers in P - {d} are
the same brand. Furthermore, d e P - {c}, and, also by inductive hypothesis, all the
computers in P - {c} are the same brand. Now, let e be a computer in both P - {cl
and P - {d}. Then, d is the same brand as e, and c is the same brand as e. Therefore,
d is the same brand as c. - Using the Principle of Mathematical Induction, prove each of the following different
forms of the principle:
(a) Induction with a possibly negative starting point: Suppose that S C Z, that some
integer no E S, and that for every n E Z, if n e S and n > no, then n + 1 E S.
Then, for every integer n > no, we have n E S.
(b) Induction downward: Suppose that S C Z, that some integer no E S, and that for
every n e Z, if n E S and n < no, then n -1 e S. Then, for every integer n < no,
we have n e S.
(c) Finite induction upward: Let no, nI E Z, no < nI. Suppose that S C Z, no E S,
and for every n e Z, if n e S, n > no, and n < ni, then n + 1 e S. Then, every
integer n where no < n < nI is in S.
(d) Suppose S C N is infinite, and suppose that for every n E N, if n + 1 E S, then
n c S. Prove that S = N.
Strong Form of Mathematical Induction
The Fundamental Theorem of Arithmetic states some familiar results about factoring
integers. Part of the Fundamental Theorem of Arithmetic is the result that every integer
n > 1 can be factored as a productn = P1 "P2." Pk