Mathematical Induction
Theorem 1: Prove that
n(n + 1)
2
1 + 2 + 3 + ... + n =
()
for any integer n 1.
Proof:
STEP 1: For n=1 () is true, since
1=
1(1 + 1)
.
2
STEP 2: Suppose () is true for some n = k 1, that is
1 + 2 + 3 + ... + k =
k(k + 1)
.
2
STEP 3: Prove that () is true for n = k + 1, that is
?
1 + 2 + 3 + . . . + k + (k + 1) =
(k + 1)(k + 2)
.
2
We have
k(k + 1)
1 + 2 + 3 + . . . + k + (k + 1) =
+ (k + 1) = (k + 1)
2
ST.2
k
(k + 1)(k + 2)
+1 =
.
2
2
Theorem 2: Prove that
1 + 3 + 5 + . . . + (2n 1) = n2
for any integer n 1.
Proof:
STEP 1: For n=1 () is true, since 1 = 12 .
STEP 2: Suppose () is true for some n = k 1, that is
1 + 3 + 5 + . . . + (2k 1) = k 2 .
STEP 3: Prove that () is true for n = k + 1, that is
?
1 + 3 + 5 + . . . + (2k 1) + (2k + 1) = (k + 1)2 .
ST.2
We have: 1 + 3 + 5 + . . . + (2k 1) + (2k + 1) = k 2 + (2k + 1) = (k + 1)2 .
()
Theorem 3: Prove that
n! nn
()
for any integer n 1.
Proof:
STEP 1: For n=1 () is true, since 1! = 11 .
STEP 2: Suppose () is true for some n = k 1, that is k! k k .
?
STEP 3: Prove that () is true for n = k + 1, that is (k + 1)! (k + 1)k+1 . We have
ST.2
(k + 1)! = k! (k + 1) k k (k + 1) < (k + 1)k (k + 1) = (k + 1)k+1 .
Theorem 4: Prove that
32n 1 div. by 8
()
for any integer n 0.
Proof:
STEP 1: For n=0 () is true, since 30 1 is divisible by 8.
STEP 2: Suppose () is true for some n = k 0, that is 32k 1 is divisible by 8.
STEP 3: Prove that () is true for n = k + 1, that is 32(k+1) 1 is divisible by 8. We have
32(k+1) 1 = 32k+2 1 = 32k 9 1 = 32k (8 + 1) 1 = |32k{z 8} + 3| 2k{z 1} .
div. by 8
St. 2
div. by 8
PROBLEMS
I. Prove by induction the following identities:
n(n + 1)
.
2
1.
1 + 2 + 3 + ... + n =
2.
1 + 3 + 5 + . . . + (2n 1) = n2 .
3.
12 + 22 + 32 + . . . + n2 =
4.
1 2 + 2 3 + 3 4 + . . . + (n 1)n =
5.
1
1
1
1
n1
+
+
+ ... +
=
.
12 23 34
(n 1)n
n
6.
7.
8 .
n(n + 1)(2n + 1)
.
6
n(n 1)(n + 1)
.
3
1
1
1
1
n
+
+
+ ... +
=
.
13 35 57
(2n 1)(2n + 1)
2n + 1
1
1
1
1
1
1
1
1
... 1
= .
2
3
4
n
n
1
1
1
1
+
+
+ ... +
= n 1.
n1+ n
1+ 2
2+ 3
3+ 4
sin
9 . sin + sin 2 + sin 3 + . . . + sin n =
(n + 1)
n
sin
2
2
.
sin
2
II. Prove by induction the following inequalities:
1.
2n > n for any integer n 1.
2.
n! > n2 for any integer n 4.
3.
2n < n! for any integer n 4.
4.
3n < n! for any integer n 7.
5.
3n 2n + 1 for any integer n 1.
6.
n! nn for any integer n 1.
7.
2n+2 2n + 5 for any integer n 1.
8 .
(2n)! < 22n (n!)2 for any integer n 1.
9 .
(n + 1)n < nn+1 for any integer n 3.
n
an1 + an2
a1 + a2
for any positive numbers a1 , a2 and for any integer n 1.
2
2
10 .
11 .
1
1
1
1
+ 2 + 2 + . . . + 2 < 2 for any integer n 1.
2
1
2
3
n
III. Prove by induction the following problems:
1.
n3 n is divisible by 3 for any nonnegative integer n.
2.
n5 n is divisible by 5 for any nonnegative integer n.
3.
n3 7n + 3 is divisible by 3 for any nonnegative integer n.
4.
4n 1 is divisible by 3 for any nonnegative integer n.
5.
32n 1 is divisible by 8 for any positive integer n.
6.
7n 2n is divisible by 5 for any nonnegative integer n.
7 .
32n+3 + 40n 27 is divisible by 64 for any nonnegative integer n.
8 .
52n+1 2n+2 + 3n+2 22n+1 is divisible by 19 for any nonnegative integer n.
!n
!n !
1
1
+
5
1
5
9 .
is integer for any nonnegative integer n.
2
2
5
Theorem : Prove that
1 + 2 + 3 + ... + n =
Proof :
n(n + 1)
for any integer n 1.
()
STEP1 : For n = 1 () is true, since
1(1 + 1)
.
1=
2
STEP2 : Suppose () is true for some
n = k 1, that is
k(k + 1)
1 + 2 + 3 + ... + k =
.
2
STEP3 : Prove that () is true for n = k + 1 :
? (k + 1)(k + 2)
.
1 + 2 + 3 + . . . + k + (k + 1) =
2
We have :
1 + 2 + 3 + . . . + k + (k + 1)
ST.2 k(k + 1)
=
+ (k + 1)
2
(k + 1)(k + 2)
=
.
2
Theorem : Prove that
1 + 3 + 5 + . . . + (2n 1) = n2
for any integer n 1.
()
Proof :
STEP1 : For n = 1 () is true, since
1 = 12 .
STEP2 : Suppose () is true for some
n = k 1, that is
1 + 3 + 5 + . . . + (2k 1) = k2.
STEP3 : Prove that () is true for n = k + 1 :
?
1 + 3 + 5 + . . . + (2k 1) + (2k + 1) = (k + 1)2.
We have :
1 + 3 + 5 + . . . + (2k 1) + (2k + 1)
ST.2
= k2 + (2k + 1)
= (k + 1)2.
Theorem : Prove that
n! nn
for any integer n 1.
()
Proof :
STEP1 : For n = 1 () is true, since
1! = 11.
STEP2 : Suppose () is true for some
n = k 1, that is :
k! kk .
STEP3 : Prove that () is true for n = k + 1
?
(k + 1)! (k + 1)k+1.
We have :
ST.2
(k + 1)! = k! (k + 1) kk (k + 1)
< (k + 1)k (k + 1)
= (k + 1)k+1.
Theorem : Prove that
32n 1 div. by 8
for any integer n 0.
()
Proof :
STEP1 : For n = 0 () is true, since
30 1 div. by 8.
STEP2 : Suppose () is true for some
n = k 0, that is
32k 1 div. by 8.
STEP3 : Prove that () is true for n = k + 1 :
?
2(k+1)
3
1 div. by 8.
We have :
2k 8 + 32k 1 .
32(k+1) 1 = 32k 9 1 = 3
| {z } | {z }
div. by
St. 2
div. by 8
