Bridge to Abstract Mathematics: Mathematical Proof and Structures

342 .CONSTRUCTION OF NUMBER SYSTEMS Chapter 10

The second induction principle IP2 [(c) of Theorem 111 is occasionally

useful in writing a more streamlined induction proof than would be possible

with only IP at our disposal [see Exercise 8(b)]. An example of this follows.

EXAMPLE 1 Given n E N, we define the nth Fibonacci number f, by the

rules fl = f2 =1 and f,+, =f, +f,+, when n 2 1. Use IP2 to prove

that f, E N for each n E N.

Solution Let S = {n E ~lf, EN}. We claim S = N, and will use IP2 to

prove it. Clearly 1 E S since fl = 1 E N. Suppose now that m IS N

and that k E S for each k = l,2,... , m. We claim m + 1 E S; that is,

fm+ , E N. But fm+ = fm- + fm, the sum of two positive integers by the

induction hypothesis, and thus a positive integer, by closure.

Exercises

1. Give a formal definition by induction for each of the following quantities, defined
   informally here. In each case n E N.
   (a) n factorial, denoted n!, equal to the product n(n - l)(n - 2) - - (3)(2)(1)
   *(b) nth power of x, where x E R, denoted xO, equal to the product (x)(x) -.. (x), n
   times
   (c) The sum of n copies of a real number a, denoted nu, equal to a + a + - - + a, n
   times
   (d) The union of n sets, XI, X,,... , X,, equal to XI u X, u. - - u X,
   (e) Composition of n functions with domain R and range a subset of R, de-
   noted f,of,-, O~,-,O...O f20 fl, where (f,of,-, ~f,-~o-..o f20 fl)(x)=
   (f,(f,- df,-2... (f2(fl(~))). -9) for all x E R
   (f) The nth Fibonacci number f,, where the first two Fibonacci numbers are
   defined to equal 1, and where all other Fibonacci numbers equal the sum of the
   two preceding such numbers.


2. (a) (This exercise relates to the proof of Theorem 3.) Consider the collec-
   tion 6 of all relations r, on N (i.e., each r, is a subset of N x N) satisfying
   (i)' (1, o(m)) E I,, and (ii)' (n, p) E r, implies (~(n), a(p)) E r, for any n, p E N.
   Let s, = n {r,(r, E 6). Prove that
   (i) s, satisfies (i)' and (ii)'
   (ii) If c E a, then s, c c [i.e., s, is the "smallest" relation on N satisfying (i)', (ii)']
   (b) Prove Theorem 4. (Mimic the proof, given in the text, of Theorem 3.)


3. This exercise relates to the proof of Theorem 5.
   (a) Prove Theorem 5(a); that is, addition on N is associative.
   *(b) Prove that 4m) = 1 + m = sl(m) for any m E N. [This is the lemma used in
   the proof of Theorem 5(b).]
   (c) Prove the "left-additive cancellation" property of N, that is, prove that if
   n, p, q E N with q + n = q + p, then n = p.