Module 2: Properties of Integers

Mathematical Induction
The method of mathematical induction is based on a principle called the
Induction Principle. This principle is based on another principle known
as the Well-ordering Principle.

Well-ordering Principle
Every non-empty subset of Z+ contains a smallest (least) element.
(OR) The set of all positive integers is well-ordered.

Induction Principle (Principle of Mathemati-

cal Induction)
Let S(n) denote an open statement that involves a positive integer n. Sup-
pose that the following conditions hold:
1. S(1) is true.
2. If whenever S(k) is true for some particular, arbitrarily chosen k ∈ Z+ ,
then S(k + 1) is true.
Then S(n) is true for all n ∈ Z+ .

Method of Mathematical Induction

Suppose we wish to prove that a statement S(n) is true for all n ≥ 1. The
method of proving this using the principle of induction is called the Method
of Mathematical Induction.

1
Steps in Mathematical Induction
1. Basis Step: Verify that S(n) is true for n = 1.

2. Induction Step: Assume that S(k) is true for some k ≥ 1, and then
show that S(k + 1) is true.

Note
Suppose we require to prove a statement S(n) for n ≥ n0 , where n0 is an
integer. In such a situation:

• Verify that S(n0 ) is true (Basis Step).

• In the induction step, assume k ≥ n0 and prove S(k + 1) is true.

Problem 1
Prove by mathematical induction that, for all positive integers n ≥
1,
1
1 + 2 + 3 + 4 + · · · + n = n(n + 1)
2

2
 Proof:
Let
1
S(n) : 1 + 2 + 3 + · · · + n = n(n + 1)
2
for all integers n ≥ 1.
Basis step: For n = 1,
1
1= · 1 · (1 + 1)
2
which is true. Hence, S(1) is true.
Induction step: Assume that the statement is true for n = k, where
k ≥ 1:
1
S(k) : 1 + 2 + 3 + · · · + k = k(k + 1)
2
Now consider n = k + 1:

(1 + 2 + 3 + · · · + k) + (k + 1)

Using the assumption:

 
1 k 1
= k(k + 1) + (k + 1) = (k + 1) +1 = (k + 1)(k + 2)
2 2 2

This is precisely the statement S(k + 1). By mathematical induction, the

result holds for all n ≥ 1.

Problem 2
Prove that, for each n ∈ Z+ ,
1
12 + 22 + 32 + · · · + n2 = n(n + 1)(2n + 1)
6
Proof:
Let S(n) denote the given statement.
Basis step:
For n = 1,
1
12 = × 1 × 2 × 3
6

3
which is true. Hence, S(1) is true.
Induction step:
Assume that S(n) is true for n = k, where k ≥ 1, i.e.,
1
S(k) : 12 + 22 + 32 + · · · + k 2 = k(k + 1)(2k + 1)
6
Now consider n = k + 1:

12 + 22 + 32 + · · · + k 2 + (k + 1)2

Using the assumption,

1
= k(k + 1)(2k + 1) + (k + 1)2
6
 
k(2k + 1)
= (k + 1) + (k + 1)
6
 2 
2k + k + 6k + 6
= (k + 1)
6
1
= (k + 1)(k + 2)(2k + 3)
6
This is precisely the statement S(k + 1).
Thus, the statement S(k + 1) is true whenever S(k) is true. Hence, by
mathematical induction, the result holds for all n ∈ Z+ .

Problem 3
Prove, by mathematical induction, that
1
12 + 32 + 52 + · · · + (2n − 1)2 = n(2n − 1)(2n + 1)
3
for all integers n ≥ 1.
Proof:
Let S(n) denote the given statement.
Basis step:

4
 For n = 1,
1
12 = ×1×1×3
3
which is true. Hence, S(1) is true.
Induction step:
Assume that S(n) is true for n = k, where k ≥ 1, i.e.,
1
12 + 32 + 52 + · · · + (2k − 1)2 = k(2k − 1)(2k + 1)
3
Now consider n = k + 1:

12 + 32 + 52 + · · · + (2k − 1)2 + (2k + 1)2

Using the assumption,

1
= k(2k − 1)(2k + 1) + (2k + 1)2
3

1
= (2k + 1) [k(2k − 1) + 3(2k + 1)]
3
1
= (2k + 1)(2k 2 + 5k + 3)
3
1
= (2k + 1)(k + 1)(2k + 3)
3
This is precisely the statement S(k + 1).
Thus, the statement S(k + 1) is true whenever the statement S(k) is true.
Hence, by mathematical induction, S(n) is true for all integers n ≥ 1.

Problem 4
If n is any positive integer, prove that
1
1 · 2 + 2 · 3 + 3 · 4 + · · · + n(n + 1) = n(n + 1)(n + 2)
3
using mathematical induction.
Proof:
Let S(n) denote the given statement.

5
 Basis step:
For n = 1,
1
1 · 2 = (1 × 2 × 3)
3
which is true. Hence, S(1) is true.
Induction step:
Assume that S(n) is true for n = k, where k ≥ 1, i.e.,
1
1 · 2 + 2 · 3 + 3 · 4 + · · · + k(k + 1) = k(k + 1)(k + 2)
3
Now consider n = k + 1:

1 · 2 + 2 · 3 + 3 · 4 + · · · + k(k + 1) + (k + 1)(k + 2)

Using the assumption,

1
= k(k + 1)(k + 2) + (k + 1)(k + 2)
3
 
k
= (k + 1)(k + 2) +1
3
1
= (k + 1)(k + 2)(k + 3)
3
This is precisely the statement S(k + 1).
Thus, the statement S(k + 1) is true whenever S(k) is true. Hence, by
mathematical induction, the result holds for all integers n ≥ 1.

Problem 5
Prove that
4n < (n2 − 7)
for all positive integers n ≥ 6.
Proof:
Let
S(n) : 4n < (n2 − 7)
for all positive integers n ≥ n0 , where n0 = 6.

6
 Basis step:
For n = 6,
4 × 6 < 62 − 7
24 < 36 − 7 = 29
which is true. Hence, S(6) is true.
Induction step:
Assume that S(n) is true for n = k, where k ≥ 6, i.e.,

4k < k 2 − 7

Now consider n = k + 1:

4(k + 1) = 4k + 4

Using the assumption,

< (k 2 − 7) + 4
Since for k ≥ 6, we have 2k + 1 ≥ 13 > 4, it follows that

(k 2 − 7) + 4 < (k 2 − 7) + (2k + 1)

= (k + 1)2 − 7
Thus,
4(k + 1) < (k + 1)2 − 7
This shows that S(k + 1) is true.
By mathematical induction, the statement S(n) is true for all positive
integers n ≥ 6.

Problem 6
Let Hn be defined as in the preceding example. Prove that
n
X n(n + 1) n(n + 1)
jHj = Hn+1 −
j=1
2 4

for all positive integers n ≥ 1.

Proof:

7
 Let S(n) denote the statement to be proved.
Basis step:
For n = 1,
2·1 2·1
H1 = H2 −
2 4
i.e.,  
1 1
1=1· 1+ −
2 2
which is true. Hence, S(1) is true.
Induction step:
Assume that S(n) is true for n = k ≥ 1, i.e.,
k
X (k + 1)k (k + 1)k
jHj = Hk+1 −
j=1
2 4
Now consider n = k + 1:
k+1
X k
X
jHj = jHj + (k + 1)Hk+1
j=1 j=1

Using the assumption,

 
(k + 1)k (k + 1)k
= Hk+1 − + (k + 1)Hk+1
2 4
  
k k
= (k + 1) + 1 Hk+1 −
2 4
1
Using Hk+2 = Hk+1 + k+2 ,
   
k 1 k
= (k + 1) +1 Hk+2 − −
2 k+2 4
 
k+2 1 k
= (k + 1) Hk+2 − −
2 2 4
 
k+2 k+2
= (k + 1) Hk+2 −
2 4
(k + 2)(k + 1) (k + 2)(k + 1)
= Hk+2 −
2 4
This is precisely the statement S(k + 1).
Hence, by mathematical induction, S(n) is true for all positive integers.

8
Problem 7
Prove that every positive integer n ≥ 24 can be written as a sum
of 5’s and/or 7’s.
Proof:
Here, we have to prove that the statement

S(n) : n can be written as a sum of 5’s and/or 7’s

is true for all integers n ≥ 24.

Basis step: We note that

24 = (7 + 7) + (5 + 5)

This shows that S(24) is true.

Induction step: We assume that S(n) is true for n = k where k ≥ 24.
Then
k = (7 + 7 + . . . ) + (5 + 5 + . . . )
Suppose this representation of k has r number of 7’s and s number of 5’s.
Since k ≥ 24, we should have r ≥ 2 and s ≥ 2.
Using this representation of k, we find that:
 

k + 1 = (7 + 7 + . . . ) + (5 + 5 + . . . ) + 1
| {z } | {z }
r s

= (7 + 7 + . . . ) +(7 + 7) + (5 + 5 + . . . ) +1
| {z } | {z }
(r−2) s

= (7 + 7 + . . . ) + (5 + 5 + . . . )
| {z } | {z }
(r−2) (s+3)

(Note: This works because 2 × 7 = 14, and 14 + 1 = 15, which is 3 × 5.

So, we replace two 7’s with three 5’s to increase the total by 1).
This shows that (k + 1) is a sum of 7’s and 5’s. Thus, S(k + 1) is true.
Conclusion: Hence, by mathematical induction, S(n) is true for all
positive integers n ≥ 24.

9
Rules of Sum and Product
The Sum Rule
If T1 and T2 are two tasks such that T1 can be performed in m different ways,
T2 can be performed in n different ways, and if these two tasks cannot be
performed simultaneously, then one of the tasks T1 or T2 can be performed
in m + n ways.
Example: Suppose a library has 12 books on Mathematics, 10 books on
Physics, and 16 books on Computers. If a student wishes to choose one of
these books to study, then the number of ways he can choose the book is:
10 + 12 + 16 = 38

The Product Rule

If T1 and T2 are two tasks such that T1 can be performed in m different ways
and for each of these ways, T2 can be performed in n different ways, then
both the tasks can be performed in m × n different ways.
Example: Suppose a person has 8 shirts and 5 ties. Then the number
of ways of choosing a shirt and a tie is:
8 × 5 = 40

Problems on Counting
Problem 1
Cars of a particular company come in 4 models, 12 colors, 3 engine sizes and
2 transmission types.
(i) How many distinct cars of this company can be manufactured?
(ii) Of these, how many have the same color?
Solution:
(i) Total number of distinct cars:
4 × 12 × 3 × 2 = 288
(ii) For any chosen color:
4 × 3 × 2 = 24

10
Problem 2
A license plate consists of 2 letters followed by 4 digits.
In how many ways can this be done if:

(i) No letter or digit can be repeated.

(ii) Repetitions are allowed.

(iii) Only vowels and even digits can be used (with repetition).

Solution:

(i) Letters: 26 × 25 (no repetition)

Digits: 10 × 9 × 8 × 7

26 × 25 × 10 × 9 × 8 × 7 = 32, 76, 000

(ii)
26 × 26 × 10 × 10 × 10 × 10 = 67, 60, 000

(iii) Vowels = 5, Even digits = 5

5 × 5 × 5 × 5 × 5 × 5 = 15, 625

Problem 3
Determine the number of 6-digit integers (no leading zero) in which:

(i) No digit is repeated.

(ii) No digit is repeated and the number is even.

(iii) No digit is repeated and the number is divisible by 5.

Solution:

(i)
9 × 9 × 8 × 7 × 6 × 5 = 1, 36, 080

11
 (ii) Last digit must be even: {0, 2, 4, 6, 8}
Case 1: Last digit = 0

9 × 8 × 7 × 6 × 5 × 1 = 15, 120

Case 2: Last digit = 2,4,6,8 (4 choices)

8 × 8 × 7 × 6 × 5 × 4 = 53, 760

Total:
15, 120 + 53, 760 = 68, 880

(iii) Last digit must be 0 or 5

Case 1: Last digit = 0

9 × 8 × 7 × 6 × 5 × 1 = 15, 120

Case 2: Last digit = 5

8 × 8 × 7 × 6 × 5 × 1 = 13, 440

Total:
15, 120 + 13, 440 = 28, 560

Problem 6
Find the number of proper divisors of 441000.
Note: Proper divisors exclude 1 and the number itself.

Solution
Prime factorization:
441000 = 23 · 32 · 53 · 72
Any divisor is of the form:

d = 2 p · 3q · 5r · 7s

12
where
0 ≤ p ≤ 3, 0 ≤ q ≤ 2, 0 ≤ r ≤ 3, 0≤s≤2
Number of choices:

(3 + 1)(2 + 1)(3 + 1)(2 + 1) = 4 × 3 × 4 × 3 = 144

Thus, total number of divisors = 144.

Proper divisors exclude 1 and 441000:

144 − 2 = 142

13