文档介绍：Chapter 4 Properties of the Integer: Mathematical Induction
vq321@梁博
-007@陳滬峰
czhina@ 陳再輝
wumeng8619@吳萌
Biying_1128@畢瑩
期中問卷:/
1
Chap 4 Properties of the Integers
The Well-Ordering Principle: Mathematical Induction
The Well-Ordering Principle: Every nonempty subset of Z+ contains a smallest element. ( )
The Principle of Mathematical Induction: Let S(n) denote an open mathematical statement that involves one or more occurrences of the variable n, which represents a positive integer.
If S(1) is true; and (basis step)
If whenever S(k) is true, then S(k+1) is true. (inductive step)
then S(n) is true for all
Using quantifiers
2
Chap 4 Properties of the Integers
The Well-Ordering Principle: Mathematical Induction
Example : For any
Proof
3
Chap 4 Properties of the Integers
The Well-Ordering Principle: Mathematical Induction
Example : Among the 900 three-digit integers (100 to 999), where the integer is the same whether it is read from left to right or from right to left, are called palindromes. Without actually determining all of these three-digit palindromes, we would like to determine their sum.
Solution
4
Chap 4 Properties of the Integers
The Well-Ordering Principle: Mathematical Induction
Example : Among the 900 three-digit integers (100 to 999), where the integer is the same whether it is read from left to right or from right to left, are called palindromes. Without actually determining all of these three-digit palindromes, we would like to determine their sum.
Solution
5
Chap 4 Properties of the Integers
The Well-Ordering Principle: Mathematical Induction
Example
For triangular number ti=1+2+…+i= i(i+1)/2
We want a formula for the sum of the first n triangular numbers.
Proof
6
Chap 4 Properties of the Integers
The Well-Ordering Principle: Mathematical Induction
Example
Consider pseudocode procedures (comparisons)
Procedure 1: n additions and n multiplications (additionally, counter i)
Proced