Mathematical Induction
Mathematical Induction
Mathematical Induction
p.1
Theorem 1 ( Principle of Mathematical Induction) Suppose A is a subset of with the properties : [1a] 1 A ; [1b] k A implies k +1 A. Then A = N. Theorem 2 ( The Strong Principle of Mathematical Induction) Suppose A is a subset of with the properties : [2a] 1 A ; [2b] {1, 2,, k } A implies k +1 A. Then A = N.
In the applications, if we want to prove some statements regarding natural numbers, we may assume P[n] is the statement that the positive integer n has property P. Then , follow the following two steps: [Step I] Prove that P[1] is true. [Step II] Prove that P[k] P[k+1]. Here, we assume that A= { n : P[n] is true } . Then the [Step I] say: 1 A; and [Step II] say: k A implies k +1 A. By the Principle of Mathematical Induction, we have A = N. Thus means: n P[n] is true. Sometimes, we might need to use Theorem 2 to prove that n P[n] is true. We shall follow the following two steps: [Step I] Prove that P[1] is true. [Step II] * : Prove that n k P[k] P[k+1]. In the following , we shall use Mathematical Induction ( or other methods) to prove some identities. We also use : LHS and RHS to denote the left hand side of and the right hand side of the formula under discussion.
p.2
If A is a non-empty set, then there is a minimum number m in A. Proof: Assume , in the contrary, there exist a non-empty subset A of which has no minimum number. Let B : = - A. Then either B = or B . But, for the case B = , we have A = , and has minimum number 1, a contradiction to the assumption that the set A has no minimum number. Thus,
- A = B .
Now, since 1 is the minimum positive number in , and A has no minimum number in it, 1 B. Assume that { 1,2,, k} B. Then
k +1 a
for all a A.
Since the set A contains no minimum number, k+1 is not a member of A. This means:
k + 1 B.
Thus, A is a empty set. This contradict to the assumption that A is a non-empty set. Therefore, we have prove the conclusion: any non-empty subset of has a minimum number.
Mathematical Induction
p.3
Theorem 4
n
j
j=1
n(n + 1) 2
(1)
Proof:
n
Let P[n] : =
j
j=1
n(n + 1) 2
j
j=1
k(k + 1) . 2
LHS =
j
j=1
j
j=1
+ (k+1)
Mathematical Induction
p.4
Theorem 5
n
j
j=1
n(n + 1)(2n + 1) 6
(2)
Proof:
n
j
j=1
n(n + 1)(2n + 1) 6
LHS = 12 = 1
[Step 2 ]
j
j=1
k(k + 1)(2k + 1) . 6
LHS =
j
j=1
j
j=1
+ (k + 1)2 =
k(k + 1)(2k + 1) + (k + 1) 2 6
n(n + 1)(2n + 1) = RHS. 6 Hence, P[k] is true P[k+1] is true. = Applying the Principle of Mathematical Induction,
Mathematical Induction
n
p.5
j
j=1
n(n + 1)(2n + 1) 6
Remark:
n
An alternative way to derive the formula for Start with the observation :
j
j=1
is the following :
{( j + 1)3 j3} =
j=1
{3j2 + 3j + 1} =
j=1 n j=1 n j=1
This implies:
n
(n + 1) Hence,
n
n(n + 1) +n. 2
3 {j2 } = { (n + 1)
j=1
- 1} -
3n(n + 1) -n 2 3n(n + 1) n 2
= (n 3 + 3n 2 + 3n + 1) 1
= n 3 + 3n 2 + 2n
= This means:
n
j
j=1
Mathematical Induction
p.6
j
j=1
(3)
j
j=1 2m
j
j=1
8 j2
j=1
(2m)(2m + 1)(4m + 1) m(m + 1)(2m + 1) 8 6 6 m {(2m + 1)(4m + 1) 4(m + 1)(2m + 1)} 3 m {(8m 2 + 6m + 1) 4(2m 2 + 3m + 1)} 3 m {6m 3} 3 (4)
= -m(2m+1) = n(n + 1) . 2
Mathematical Induction
p.7
= ( 2m+1)(-m+2m+1) = (2m+1)(m+1) = n( n 1 + 1) 2
Theorem 6
12 2 2 + 32 + .... + (1) n +1 n 2 = n(n + 1) { [[ n is odd]] [[n is even]]}. 2
Sometimes, we may use Mathematical Induction method to prove some inequalities. Here is an example.
Proof:
Let P[n] = n = 1. 1 = 0. 1 1 1 1 + + ... + 2 n - 1 . 1 2 n
[Step 1]
Mathematical Induction
p.8
[Step 2] Assume that P[k] is true,. i.e. For the case n = k+1, we have RHS LHS = {2 k + 1 1} {
1 1 1 + + ... + 2 k 1 . 1 2 k
1 1 1 1 + + ... + + } 1 2 k k +1
= {2 k 1} {
2 k +1 2 k
0. Thus, P[ k+1] is true. Applying the Principle of Mathematical induction, we have: 1 1 1 + + ... + 2 n - 1 for every positive integer. 1 2 n