数学归纳法(英文版).ppt

Chapter 4 Properties of the Integers: Mathematical Induction? Introduction Mathematical induction 數學歸納法 is a technique exhibited by the subset of positive integers. Four sets of numbers that are very important in the study of discrete mathematics and combinatorics are introduced – namely, the harmonic numbers調和數列, the Fibonacci numbers費伯納西數列, the Lucas numbers, and the Eulerian numbers. When x, y ? Z, we know that x + y, xy, x – y ? Z. Thus we say that the set Z is closed under (the binary operations of) addition, multiplication, and subtraction. Note that 2, 3 ? Z but that the rational number 2/3 is not a member of Z. So the set Z of all integers is not closed under the binary operation of nonzero division. A special concentration on primes (? Z+). 4.1 The Well-Ordering Principle: Mathematical Induction The Well-Ordering Principle (of positive integers): Every nonempty subset of Z+ contains a smallest element. (often saying that Z+ is well ordered) The set Z+ is different from the sets Q+ and R+ in that every nonempty subset X of Z+ contains an integer a such that a ? x, for all x ? X. Theorem 4.1: Finite Induction Principle, or Principle of Mathematical Induction. Let S(n) denote an open mathematical statement (or set of such open statements) the involves one or more occurrences of the variable n, which represents a positive integer. If S(1) is true (referred to as the basic step); and If whenever S(k) is true (for some particular, but arbitrarily chosen, k ? Z+), then S(k +1) is true (called the inductive step); then S(n) is true for all n ? Z+. Mathematical Induction Proof: see page 164. The choice of 1 in the first condition of Theorem 4.1 is not mandatory. If the true of S(n0) is for our basic step (a different starting point!), we can rewrite the Finite Induction Principle, using quantifiers, as [S(n0) ? [? k ? n0 [S(k) ? S(k + 1)]]] ? ? n ? n0 S(n). Example 4.1: page 166. Example 4.3: page 167. Example 4.4: page 168. (This example indicat