vAnalysis and natural philosophy owe their most important discoveries to

this fruitful means, which is called induction. Newton was indebted

to it for his theorem of the binomial and the principle of

universal gravity. – LAPLACE v

4.1 Introduction

One key basis for mathematical thinking is deductive rea-

soning. An informal, and example of deductive reasoning,

borrowed from the study of logic, is an argument expressed

in three statements:

(a) Socrates is a man.

(b) All men are mortal, therefore,

(c) Socrates is mortal.

If statements (a) and (b) are true, then the truth of (c) is

established. To make this simple mathematical example,

we could write:

(i) Eight is divisible by two.

(ii) Any number divisible by two is an even number,

therefore,

(iii) Eight is an even number.

Thus, deduction in a nutshell is given a statement to be proven, often called a

conjecture or a theorem in mathematics, valid deductive steps are derived and a

proof may or may not be established, i.e., deduction is the application of a general

case to a particular case.

In contrast to deduction, inductive reasoning depends on working with each case,

and developing a conjecture by observing incidences till we have observed each and

every case. It is frequently used in mathematics and is a key aspect of scientific

reasoning, where collecting and analysing data is the norm. Thus, in simple language,

we can say the word induction means the generalisation from particular cases or facts.

Chapter

4

PRINCIPLE OF

MATHEMATICAL INDUCTION

G . Peano

(1858-1932)

2020-21

PRINCIPLE OF MATHEMATICAL INDUCTION 87

In algebra or in other discipline of mathematics, there are certain results or state-

ments that are formulated in terms of n, where n is a positive integer. To prove such

statements the well-suited principle that is used–based on the specific technique, is

known as the principle of mathematical induction.

4.2 Motivation

In mathematics, we use a form of complete induction called mathematical induction.

To understand the basic principles of mathematical induction, suppose a set of thin

rectangular tiles are placed as shown in Fig 4.1.

Fig 4.1

When the first tile is pushed in the indicated direction, all the tiles will fall. To be

absolutely sure that all the tiles will fall, it is sufficient to know that

(a) The first tile falls, and

(b) In the event that any tile falls its successor necessarily falls.

This is the underlying principle of mathematical induction.

We know, the set of natural numbers N is a special ordered subset of the real

numbers. In fact, N is the smallest subset of R with the following property:

A set S is said to be an inductive set if 1∈ S and x + 1 ∈ S whenever x ∈ S. Since

N is the smallest subset of R which is an inductive set, it follows that any subset of R

that is an inductive set must contain N.

Illustration

Suppose we wish to find the formula for the sum of positive integers 1, 2, 3,...,n, that is,

a formula which will give the value of 1 + 2 + 3 when n = 3, the value 1 + 2 + 3 + 4,

when n = 4 and so on and suppose that in some manner we are led to believe that the

formula 1 + 2 + 3+...+ n =

( 1)

2

n n

+

is the correct one.

How can this formula actually be proved? We can, of course, verify the statement

for as many positive integral values of n as we like, but this process will not prove the

formula for all values of n. What is needed is some kind of chain reaction which will

2020-21

88 MATHEMATICS

have the effect that once the formula is proved for a particular positive integer the

formula will automatically follow for the next positive integer and the next indefinitely.

Such a reaction may be considered as produced by the method of mathematical induction.

4.3 The Principle of Mathematical Induction

Suppose there is a given statement P(n) involving the natural number n such that

(i) The statement is true for n = 1,

i.e., P(1) is true, and

(ii) If the statement is true for n = k

(where k is some positive integer), then

the statement is also true for n = k + 1, i.e., truth of P(k) implies the

truth of P (k + 1).

Then, P(n) is true for all natural numbers n.

Property (i) is simply a statement of fact. There may be situations when a

statement is true for all n ≥ 4. In this case, step 1 will start from n = 4 and we shall

verify the result for n = 4, i.e., P(4).

Property (ii) is a conditional property. It does not assert that the given statement

is true for n = k, but only that if it is true for n = k, then it is also true for n = k +1. So,

to prove that the property holds , only prove that conditional proposition:

If the statement is true for n = k, then it is also true for n =

k + 1.

This is sometimes referred to as the inductive step. The assumption that the given

statement is true for n = k in this inductive step is called the inductive hypothesis.

For example, frequently in mathematics, a formula will be discovered that appears

to fit a pattern like

1 = 1

2

=1

4 = 2

2

= 1 + 3

9 = 3

2

= 1 + 3 + 5

16 = 4

2

= 1 + 3 + 5 + 7, etc.

It is worth to be noted that the sum of the first two odd natural numbers is the

square of second natural number, sum of the first three odd natural numbers is the

square of third natural number and so on.Thus, from this pattern it appears that

1 + 3 + 5 + 7 + ... + (2n – 1) = n

2

, i.e,

the sum of the first

n odd natural numbers is the square of n.

Let us write

P(n): 1 + 3 + 5 + 7 + ... + (2n – 1) = n

2

.

We wish to prove that P(n) is true for all

n.

The first step in a proof that uses mathematical induction is to prove that

P (1) is true. This step is called the basic step. Obviously

1 = 1

2

, i.e., P(1) is true.

The next step is called the inductive step. Here, we suppose that P (k) is true for some

2020-21

PRINCIPLE OF MATHEMATICAL INDUCTION 89

positive integer k and we need to prove that P (k + 1) is true. Since P (

k) is true, we

have

1 + 3 + 5 + 7 + ... + (2k – 1) = k

2

... (1)

Consider

1 + 3 + 5 + 7 + ... + (2k – 1) + {2(k +1) – 1} ... (2)

= k

2

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

2

[Using (1)]

Therefore, P (k + 1) is true and the inductive proof is now completed.

Hence P(n) is true for all natural numbers n.

Example 1

For all

n ≥ 1, prove that

1

2

+ 2

2

+ 3

2

+ 4

2

+…+ n

2

=

( 1)(2 1)

6

n n n

+ +

.

Solution Let the given statement be P(n), i.e.,

P(n) : 1

2

+ 2

2

+ 3

2

+ 4

2

+…+ n

2

=

( 1)(2 1)

6

n n n

+ +

For n = 1, P(1): 1 =

1(1 1)(2 1 1)

6

+ × +

=

1 2 3

1

6

× ×

=

which is true.

Assume that P(k) is true for some positive integer k, i.e.,

1

2

+ 2

2

+ 3

2

+ 4

2

+…+ k

2

=

( 1)(2 1)

6

k k k

+ +

... (1)

We shall now prove that P(k + 1) is also true. Now, we have

(1

2

+2

2

+3

2

+4

2

+…+k

2

) + (k + 1)

2

=

2

( 1)(2 1)

( 1)

6

k k k

k

+ +

+ +

[Using (1)]

=

2

( 1) (2 1) 6( 1)

6

k k k k+ + + +

=

2

( 1) (2 7 6)

6

k k k

+ + +

=

( 1)( 1 1){2( 1) 1}

6

k k k

+ + + + +

Thus P(k + 1) is true, whenever P (k) is true.

Hence, from the principle of mathematical induction, the statement P(n) is true

for all natural numbers n.

2020-21

90 MATHEMATICS

Example 2 Prove that 2

n

> n for all positive integers n.

Solution

Let P(

n): 2

n

> n

When

n =1, 2

1

>1. Hence P(1) is true.

Assume that P(k) is true for any positive integer k, i.e.,

2

k

> k ... (1)

We shall now prove that P(k +1) is true whenever P(k) is true.

Multiplying both sides of (1) by 2, we get

2. 2

k

> 2k

i.e., 2

k + 1

> 2k = k + k > k + 1

Therefore, P(

k

+ 1) is true when P(k) is true. Hence, by principle of mathematical

induction, P(n) is true for every positive integer n.

Example 3 For all n ≥ 1, prove that

1 1 1 1

...

1.2 2.3 3.4 ( 1) 1

n

n n n

+ + + + =

+ +

.

Solution We can write

P(n):

1 1 1 1

...

1.2 2.3 3.4 ( 1) 1

n

n n n

+ + + + =

+ +

We note that P(1):

1 1 1

1.2 2 1 1

= =

+

, which is true. Thus, P(n) is true for n = 1.

Assume that P(k) is true for some natural number k,

i.e.,

1 1 1 1

...

1.2 2.3 3.4 ( 1) 1

k

k k k

+ + + + =

+ +

... (1)

We need to prove that P(k + 1) is true whenever P(k) is true. We have

1 1 1 1 1

...

1.2 2.3 3.4 ( 1) ( 1) ( 2)

k k k k

+ + + + +

+ + +

=

1 1 1 1 1

...

1.2 2.3 3.4 ( 1) ( 1) ( 2)

k k k k

+ + + + +

+ + +

=

1

1 ( 1)( 2)

k

k k k

+

+ + +

[Using (1)]

2020-21

PRINCIPLE OF MATHEMATICAL INDUCTION 91

=

( 2) 1

( 1) ( 2)

k k

k k

+ +

+ +

=

2

( 2 1)

( 1) ( 2)

k k

k k

+ +

+ +

=

( )

( )( )

2

1

1 2

k

k k

+

+ +

=

( )

1 1

2 1 1

k k

k k

+ +

=

+ + +

Thus P(k + 1) is true whenever P(k) is true. Hence, by the principle of mathematical

induction, P(n) is true for all natural numbers.

Example 4 For every positive integer n, prove that 7

n

– 3

n

is divisible by 4.

Solution We can write

P(n) : 7

n

– 3

n

is divisible by 4.

We note that

P(1): 7

1

– 3

1

= 4 which is divisible by 4. Thus P(n) is true for n = 1

Let P(k) be true for some natural number k,

i.e., P(k) : 7

k

– 3

k

is divisible by 4.

We can write 7

k

– 3

k

= 4d, where d ∈

N.

Now, we wish to prove that P(k + 1) is true whenever P(k) is true.

Now 7

(k + 1)

– 3

(k + 1)

= 7

(k + 1)

– 7.3

k

+ 7.3

k

– 3

(k + 1)

= 7(7

k

– 3

k

) + (7 – 3)3

k

= 7(4d) + (7 – 3)3

k

= 7(4d) + 4.3

k

= 4(7d + 3

k

)

From the last line, we see that 7

(k + 1)

– 3

(k + 1)

is divisible by 4. Thus, P(k + 1) is true

when P(k) is true. Therefore, by principle of mathematical induction the statement is

true for every positive integer n.

Example 5 Prove that (1 + x)

n

≥ (1 + nx), for all natural number n, where x > – 1.

Solution Let P(n) be the given statement,

i.e., P(n): (1 + x)

n

≥ (1 + nx), for x > – 1.

We note that P(n) is true when n = 1, since ( 1+x) ≥ (1 + x) for x > –1

Assume that

P(k): (1 + x)

k

≥ (1 + kx), x > – 1 is true. ... (1)

We want to prove that P(k + 1) is true for x > –1 whenever P(k) is true. ... (2)

Consider the identity

(1 + x)

k + 1

= (1 + x)

k

(1 + x)

Given that x > –1, so (1+x) > 0.

Therefore , by using (1 + x)

k

≥ (1 + kx), we have

(1 + x)

k + 1

≥ (1 + kx)(1 + x)

i.e. (1 + x)

k + 1

≥ (1 + x + kx + kx

2

). ... (3)

2020-21

92 MATHEMATICS

Here k is a natural number and x

2

≥ 0 so that kx

2

≥ 0. Therefore

(1 + x

+ kx + kx

2

) ≥ (1 + x

+ kx),

and so we obtain

(1 + x)

k + 1

≥ (1 + x + kx

)

i.e. (1 + x)

k + 1

≥ [1 + (1 +

k)x]

Thus, the statement in (2) is established. Hence, by the principle of mathematical

induction, P(

n) is true for all natural numbers.

Example 6 Prove that

2.7

n

+ 3.5

n

– 5 is divisible by 24, for all n ∈ N.

Solution Let the statement P(n) be defined as

P(n) : 2.7

n

+ 3.5

n

– 5 is divisible by 24.

We note that P(n) is true for n = 1, since 2.7 + 3.5 – 5 = 24, which is divisible by 24.

Assume that P(k) is true

i.e. 2.7

k

+ 3.5

k

– 5 = 24q, when q ∈ N ... (1)

Now, we wish to prove that P(k + 1) is true whenever P(k) is true.

We have

2.7

k+1

+ 3.5

k+1

– 5 = 2.7

k

. 7

1

+ 3.5

k

. 5

1

– 5

= 7 [2.7

k

+ 3.5

k

– 5 – 3.5

k

+ 5] + 3.5

k

. 5 – 5

= 7 [24q – 3.5

k

+ 5] + 15.5

k

–5

= 7 × 24q – 21.5

k

+ 35 + 15.5

k

– 5

= 7 × 24q – 6.5

k

+ 30

= 7 × 24q – 6 (5

k

– 5)

= 7 × 24q – 6 (4p) [(5

k

– 5) is a multiple of 4 (why?)]

= 7 × 24q – 24p

= 24 (7q – p)

= 24 × r; r = 7q – p, is some natural number. ... (2)

The expression on the R.H.S. of (1) is divisible by 24. Thus P(k + 1) is true whenever

P(k) is true.

Hence, by principle of mathematical induction, P(n) is true for all n ∈ N.

2020-21

PRINCIPLE OF MATHEMATICAL INDUCTION 93

Example 7 Prove that

1

2

+ 2

2

+ ... + n

2

>

3

3

n

, n ∈ N

Solution

Let P(n) be the given statement.

i.e., P(n) : 1

2

+ 2

2

+ ... + n

2

>

3

3

n

, n ∈ N

We note that P(n) is true for n = 1 since

3

2

1

1

3

>

Assume that P(k) is true

i.e. P(k) : 1

2

+ 2

2

+ ... + k

2

>

3

3

k

...(1)

We shall now prove that P(k + 1) is true whenever P(k) is true.

We have 1

2

+ 2

2

+ 3

2

+ ... + k

2

+ (k + 1)

2

( )

( ) ( )

3

2 2

2 2 2

1 2 ... 1 1

3

k

k k k

= + + + + + > + +

[by (1)]

=

1

3

[k

3

+ 3k

2

+ 6k + 3]

=

1

3

[(k + 1)

3

+ 3k + 2] >

1

3

(k + 1)

3

Therefore, P(k + 1) is also true whenever P(k) is true. Hence, by mathematical induction

P(n) is true for all n ∈ N.

Example 8 Prove the rule of exponents (ab)

n

= a

n

b

n

by using principle of mathematical induction for every natural number.

Solution Let P(n) be the given statement

i.e. P(n) : (ab)

n

= a

n

b

n

.

We note that P(n) is true for n = 1 since (ab)

1

= a

1

b

1

.

Let P(k) be true, i.e.,

(ab)

k

= a

k

b

k

... (1)

We shall now prove that P(k + 1) is true whenever P(k) is true.

Now, we have

(ab)

k + 1

= (ab)

k

(ab)

2020-21

94 MATHEMATICS

= (a

k

b

k

) (ab) [by (1)]

= (a

k

. a

1

) (b

k

. b

1

) = a

k+1

. b

k+1

Therefore, P(k + 1) is also true whenever P(k) is true. Hence, by principle of math-

ematical induction, P(n) is true for all n ∈ N.

EXERCISE 4.1

Prove the following by using the principle of mathematical induction for all n ∈ N:

1. 1 + 3 + 3

2

+ ... + 3

n – 1

=

(3 1)

2

n

−

.

2. 1

3

+ 2

3

+ 3

3

+ … +n

3

=

2

( 1)

2

n n +

.

3.

1 1 1 2

1

(1 2) (1 2 3) (1 2 3 ) ( 1)

n

...

...n n

+ + + + =

+ + + + + + +

.

4. 1.2.3 + 2.3.4 +…+ n(n+1) (n+2) =

( 1)( 2)( 3)

4

n n n n

+ + +

.

5. 1.3 + 2.3

2

+ 3.3

3

+…+ n.3

n

=

1

(2 1)3 3

4

n

n

+

− +

.

6. 1.2 + 2.3 + 3.4 +…+ n.(n+1) =

( 1)( 2)

3

n n n+ +

.

7. 1.3 + 3.5 + 5.7 +…+ (2n–1) (2n+1) =

2

(4 6 1)

3

n n n

+ −

.

8. 1.2 + 2.2

2

+ 3.2

3

+ ...+n.2

n

= (n–1) 2

n + 1

+ 2.

9.

1 1 1 1 1

... 1

2 4 8

2 2

n n

+ + + + = −

.

10.

1 1 1 1

...

2.5 5.8 8.11 (3 1)(3 2) (6 4)

n

n n n

+ + + + =

− + +

.

11.

1 1 1 1 ( 3)

...

1.2.3 2.3.4 3.4.5 ( 1) ( 2) 4( 1) ( 2)

n n

n n n n n

+

+ + + + =

+ + + +

.

2020-21

PRINCIPLE OF MATHEMATICAL INDUCTION 95

12. a + ar + ar

2

+…+ ar

n-1

=

( 1)

1

n

a r

r

−

−

.

13.

2

2

3 5 7 (2 1)

1 1 1 ... 1 ( 1)

1 4 9

n

n

n

+

+ + + + = +

.

14.

1 1 1 1

1 1 1 ... 1 ( 1)

1 2 3

n

n

+ + + + = +

.

15. 1

2

+ 3

2

+ 5

2

+ …+ (2n–1)

2

=

(2 1)(2 1)

3

n n n

− +

.

16.

1 1 1 1

...

1.4 4.7 7.10 (3 2)(3 1) (3 1)

n

n n n

+ + + + =

− + +

.

17.

1 1 1 1

...

3.5 5.7 7.9 (2 1)(2 3) 3(2 3)

n

n n n

+ + + + =

+ + +

.

18. 1 + 2 + 3 +…+ n <

1

8

(2n + 1)

2

.

19. n (n + 1) (n + 5) is a multiple of 3.

20. 10

2n – 1

+ 1 is divisible by 11.

21. x

2n

– y

2n

is divisible by x + y.

22. 3

2n+2

– 8n – 9 is divisible by 8.

23. 41

n

– 14

n

is a multiple of 27.

24. (2n + 7) < (n + 3)

2

.

Summary

®

One key basis for mathematical thinking is deductive reasoning. In contrast to

deduction, inductive reasoning depends on working with different cases and

developing a conjecture by observing incidences till we have observed each

and every case. Thus, in simple language we can say the word ‘induction’

means the generalisation from particular cases or facts.

®

The principle of mathematical induction is one such tool which can be used to

prove a wide variety of mathematical statements. Each such statement is

assumed as P(n) associated with positive integer n, for which the correctness

2020-21

96 MATHEMATICS

for the case n = 1 is examined. Then assuming the truth of P(k) for some

positive integer k, the truth of P (k+1) is established.

Historical Note

Unlike other concepts and methods, proof by mathematical induction is not

the invention of a particular individual at a fixed moment. It is said that the principle

of mathematical induction was known by the Pythagoreans.

The French mathematician Blaise Pascal is credited with the origin of the

principle of mathematical induction.

The name induction was used by the English mathematician John Wallis.

Later the principle was employed to provide a proof of the binomial theorem.

De Morgan contributed many accomplishments in the field of mathematics

on many different subjects. He was the first person to define and name

“mathematical induction” and developed De Morgan’s rule to determine the

convergence of a mathematical series.

G. Peano undertook the task of deducing the properties of natural numbers

from a set of explicitly stated assumptions, now known as Peano’s axioms.The

principle of mathematical induction is a restatement of one of the Peano’s axioms.

—

v

v

v

v

v

—

2020-21