Scribd
Upload
111 views9 pages

Mathematical Induction Explained

Mathematical induction is a method of proof that involves two steps: 1) Showing that the statement is true for the base case (usually n=1) and 2) Assuming the statement holds true for an integer k and using this to show that the statement is also true for k+1. This implies that the statement is true for all positive integers n. The document provides examples of using mathematical induction to prove formulas for sums of integers and powers.

Uploaded by

Dane Sinclair
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
111 views9 pages

Mathematical Induction Explained

Mathematical induction is a method of proof that involves two steps: 1) Showing that the statement is true for the base case (usually n=1) and 2) Assuming the statement holds true for an integer k and using this to show that the statement is also true for k+1. This implies that the statement is true for all positive integers n. The document provides examples of using mathematical induction to prove formulas for sums of integers and powers.

Uploaded by

Dane Sinclair
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
  • Principle of Mathematical Induction
  • Introduction to Mathematical Induction
  • Example 1: Basic Induction Proof
  • Sums of Powers of Integers
  • Example 2: Advanced Induction Proof
  • Proving a Divisibility Property

Mathematical induction is a legitimate method of

proof for all positive integers n.

Principle:
Let Pn be a statement involving n, a positive integer.
If
1. P1 is true, and
2. the truth of Pk implies the truth of Pk + 1 for
every positive k,
then Pn must be true for all positive integers n.

2
Example:
Use mathematical induction to prove
Sn = 2 + 4 + 6 + 8 + . . . + 2n = n(n + 1)
for every positive integer n.

1. Show that the formula is true when n = 1.


S1 = n(n + 1) = 1(1 + 1) = 2 True
2. Assume the formula is valid for some integer k.
Use this assumption to prove the formula is valid
for the next integer, k + 1 and show that the
formula Sk + 1 = (k + 1)(k + 2) is true.
Sk = 2 + 4 + 6 + 8 + . . . + 2k = k(k + 1) Assumption
Example continues.
3
Example continued:
Sk + 1 = 2 + 4 + 6 + 8 + . . . + 2k + [2(k + 1)]

= 2 + 4 + 6 + 8 + . . . + 2k + (2k + 2)

= Sk + (2k + 2) Group terms to form Sk.

= k(k + 1) + (2k + 2) Replace Sk by k(k + 1).


= k2 + k + 2k + 2 Simplify.
= k2 + 3k + 2

= (k + 1)(k + 2)

= (k + 1)((k + 1)+1)
The formula Sn = n(n + 1) is valid for all positive integer
values of n.
4
Sums of Powers of Integers :
n
n(n  1)
1.  i  1 2  3  4 
i 1
n
2
n
n(n  1)(2n  1)
2.  i
i 1
2
 12
 2 2
 32
 4 2
  n2 
6
n 2
 2


n (n 1)
3. i 3
 13
 2 3
 33
 4 3
  n3 
i 1
4
n
  2
 3n  1)

n(n 1)(2n 1)(3n
4. i 4
 14
 2 4
 34
 4 4
 n 
4

i 1
30
n 2
 2 2
 2n  1)

n (n 1) (2n
5. i 5
 15
 2 5
 35
 4 5
 n 
5

i 1
12

5
Example:
Use mathematical induction to prove for all positive integers n,
n
n(n  1)(2n  1)
 i 2

i 1
 12
 2 2
 32
 4 2
  n2 
6
.

(  1)(2(1)  1) 1(2)(2  1) 6
11
S1    1 True
6 6 6
k (k  1)(2k  1)
Sk  12  22  32  42   k 2  Assumption
6
Sk 1  12  22  32  42   k 2  (k  1) 2
 Sk  (k  1) 2
 S k  k 2  2k  1 Group terms to form Sk.
k (k  1)(2k  1)
  k 2  2k  1 Replace Sk by k(k + 1).
6 Example continues.
6
Example continued:

 2k 3
 3k 2
 k  6k 2
 12k  6 Simplify.
6 6
 2k 3
 9k 2
 13k  6
6
(k 2  3k  2)(2k  3)

6
(k  1)(k  2)(2k  3)

6
(k  1)[(k  1)  1][2(k  1)  1]

6
The formula Sn  n(n  1)(2n  1) is valid for all positive
6
integer values of n.

7
 Proposition: For any integer n≥1,
7n - 2n is divisible by 5. (P(n))
 Proof (by induction):
1) Basis step:
The statement is true for n=1: (P(1))
71 – 21 = 7 - 2 = 5 is divisible by 5.
2) Inductive step:
Assume the statement is true for some k≥1
(P(k))
(inductive hypothesis) ;
show that it is true for k+1 . (P(k+1))

8
 Proof (cont.): We are given that
P(k): 7k - 2k is divisible by 5.
(1)
Then 7k - 2k = 5a for some aZ . (by definition)
(2)
We need to show:
P(k+1): 7k+1 - 2k+1 is divisible by 5.
(3)
7k+1 - 2k+1 = 7·7k - 2·2k = 5·7k + 2·7k - 2·2k
= 5·7k + 2·(7k - 2k) = 5·7k + 2·5a (by
(2))
= 5·(7k + 2a) which is divisible by 5. (by
def.)
Thus, P(n) is true by induction. ■
9

2 Mathematical induction is a legitimate method of proof for all positive integers n. Principle: Let Pn be a statement inv
3 Example: Use mathematical induction to prove Sn = 2 + 4 + 6 + 8 + . . . + 2n = n(n + 1) for every positive integer n. 1.
4 Example continued: Sk + 1 = 2 + 4 + 6 + 8 + . . . + 2k + [2(k + 1)] = 2 + 4 + 6 + 8 + . . . + 2k + (2k + 2) = Sk + (2k + 2)
5 Sums of Powers of Integers : 1 ( 1) 1 2 3 4 1 2 . n i n n i n         2 2 2 2 2 2 1 ( 1)(2 1) 1 2 3 4 2. 6
6 2 2 2 2 2 2 1 ( 1)(2 1) 1 2 3 4 . 6 n i n n n i n            Example: Use mathematical induction to prove for al
7 3 2 2 2 3 6 12 6 6 6 k k k k k       Simplify. Example continued: 3 2 2 9 13 6 6 k k k     2 ( 3 2)(2 3) 6 k k k
8 Proposition: For any integer n≥1, 7n - 2n is divisible by 5. (P(n)) Proof (by induction): 1) Basis step: The statemen
9 Proof (cont.): We are given that P(k): 7k - 2k is divisible by 5. (1) Then 7k - 2k = 5a for some aZ . (by definition)

You might also like