離散數學(4)

第四章 Properties of the integers: Mathematical Induction

All that is needed is for the open statement S(n) to be true for some first element n0 ε Z so that the induction process has a starting place. We need the truth of S(n0) for our basis step. The integer n0 could be 5 just as well as 1. It could even be zero or negative because the set Z+ in union with {0}{ or any finite set of negative integers is well ordered.

Principle of Mathematical Induction

[S(n0) ^ [all k>=n0[s(k) → s(k+1)]]] → all n >=no s(n)

Principle of Strong Mathematical Induction

a) If s(n0),s(n0+1), s(n0+2)...,s(n1-1),s(n1) are true

b)If whenever s(n0) s(n0+1)...s(k-1)and s(k) are true for some k ε z+, where k>=n1, then the statement s(k+1) is also true;then s(n) is true for all n>=n0

If a,b ε z and b=\0 , we say that b divides a and we write b|a, if there is an integer n such that a=bn, where this occurs we say that b is a divisor(因數), or a is a multiple(倍數) of b.

a) 1|a and a|0

b) [(a|b)^(b|a)] → a=+-b

c)[(a|b)^(b|c)] → a|c

d) a|b → a|bx for all x ε Z

e) If x=y+z for some x,y,z ε Z, and a divides two of the three integers x,y and z, then a divides the remaining integer.

f)[(a|b)^a|c)] → a|(bx+cy) for all x,y ε Z

g)For 1<=i<=n let ci ε Z. If a divides each ci, then a|(c1x1+c2x2+...+cnxn), where xi ε Z for all 1<=i<=n