Mathematical
UNIT 4 MATHEMATICAL INDUCTION Induction
Structure
4.0 Introduction
4.1 Objectives
4.2 The Principle of Mathematical Induction
4.3 Answers to Check Your Progress
4.4 Summary
4.0 INTRODUCTION
We begin with the following question. What is the sum of first n odd natural
numbers ?
If n equals 1, the sum equals 1, as 1 is the only summand. The answer we seek is
a formula that will enable us to determine this sum for each value n without
having to add the summands.
Table 4.1 lists the sum Sn of the first n odd natural numbers, as n takes values
from 1 to 10.
Table 4.1
n Series Sum (Sn)
1 1 1=12
2 1+3 4=22
3 1+3+5 9=32
4 1+3+5+7 16=42
5 1+3+5+7+9 25=52
6 1+3+5+7+9+11 36=62
7 1+3+5+7+9+11+13 49=72
8 1 +3 +……..+15 64=82
9 1 +3 +……..+17 81=92
10 1 +3 +……..+19 100=102
Jumping to a Conclusion
Judging from the pattern formed by first 10 sums, we might conjecture that
Sn = 1 + 3 + 5 + ... + (2n – 1) = n2.
Recognizing a pattern and then simply jumping to the conclusion that the pattern
must be true for all values of n is not a logically valid method of proof in 89
,Algebra - I mathematics. There are many instances when the pattern appears to be
developing for small values of n and then at some point the pattern fails. Let us
look at one example. It was widely believed that Pn = n2 + n + 41 is prime
for all natural-numbers. Indeed pn, is prime for all values of n lying between 1
and 39 as shown in Table 4.2.
But the moment we take n= 40, we get
P40 = 402 + 40 +41
= 1600+40+41 = 1681 =412
which is clearly not a prime.
Table 4.2
n Pn n Pn n Pn
1 43 11 173 26 743
12 197 27 797
2 47 13 223 28 853
3 53 14 251 29 911
15 281 30 971
4 61 16 313 31 1033
5 71 17 347 32 1097
18 383 33 1163
6 83 19 421 34 1231
7 97 20 461 35 1301
36 1373
8 113 21 503 37 1447
9 131 22 547 38 1523
23 593
10 151 24 641 39 1601
25 691
Just because a rule, pattern or formula seems to work for several values of n, we
cannot simply conclude that it is valid for all values of n without going through a
legitimate proof.
How to Legalize a Pattern?
One way to legalize the pattern is to use the principle of Mathematical
induction. To see what it is, let us return to our question in the beginning of the
90 chapter. What is the sum of first n odd natural numbers?
, We have already seen that the formula Mathematical
Induction
Sn = 1 + 3 + 5 + ... + (2n – 1) = n2 is valid for n= 1, 2, 3, ..., 10 (1)
Do we need to compute Sn by adding the first n odd natural numbers ?
A moment’s reflection will show that it is not necessary.
Having obtained the value of Sn for some integer n, we can obtain the value of
Sn+1 = Sn + 2n + 1
if Sn = n2 for some n, then Sn+1 = Sn + 2n + 1 = n2 +2n+1 = (n+1)2.
That is, if Sn = n2 for some natural number n, then the formula holds for the next
natural number n + 1.
Since the formula Sn = n2 holds for n = 10, therefore it must hold n = 11. Since,
it holds for n = 11, therefore, it must hold for n = 12. Since, it holds for n = 12,
it holds for n = 13, and so on. The principle underlying the foregoing argument is
nothing but the principle of mathematical induction. We state this formally in
section 4.3.
4.1 OBJECTIVES
After studying this unit, you should be able to:
use the principle of mathematical induction to establish truth of several
formulae and inequalities for each natural number n.
4.2 THE PRINCIPLE OF MATHEMATICAL INDUCTION
Let Pn be a statement involving the natural number n. If
1. P1 is true, and
2. the truth of Pk implies the truth of Pk+1, for every interger k, then Pn must be
true all natural numbers n.
In other words, to prove that a statement Pn holds for all natural numbers, we
must go through two steps; First, we must prove that P1 is ture. Second, we
must prove that Pk+1 is true whenever Pk is true.
CAUTION Just proving Pk+1 whenever Pk is true will not work.
An Analogue 91
UNIT 4 MATHEMATICAL INDUCTION Induction
Structure
4.0 Introduction
4.1 Objectives
4.2 The Principle of Mathematical Induction
4.3 Answers to Check Your Progress
4.4 Summary
4.0 INTRODUCTION
We begin with the following question. What is the sum of first n odd natural
numbers ?
If n equals 1, the sum equals 1, as 1 is the only summand. The answer we seek is
a formula that will enable us to determine this sum for each value n without
having to add the summands.
Table 4.1 lists the sum Sn of the first n odd natural numbers, as n takes values
from 1 to 10.
Table 4.1
n Series Sum (Sn)
1 1 1=12
2 1+3 4=22
3 1+3+5 9=32
4 1+3+5+7 16=42
5 1+3+5+7+9 25=52
6 1+3+5+7+9+11 36=62
7 1+3+5+7+9+11+13 49=72
8 1 +3 +……..+15 64=82
9 1 +3 +……..+17 81=92
10 1 +3 +……..+19 100=102
Jumping to a Conclusion
Judging from the pattern formed by first 10 sums, we might conjecture that
Sn = 1 + 3 + 5 + ... + (2n – 1) = n2.
Recognizing a pattern and then simply jumping to the conclusion that the pattern
must be true for all values of n is not a logically valid method of proof in 89
,Algebra - I mathematics. There are many instances when the pattern appears to be
developing for small values of n and then at some point the pattern fails. Let us
look at one example. It was widely believed that Pn = n2 + n + 41 is prime
for all natural-numbers. Indeed pn, is prime for all values of n lying between 1
and 39 as shown in Table 4.2.
But the moment we take n= 40, we get
P40 = 402 + 40 +41
= 1600+40+41 = 1681 =412
which is clearly not a prime.
Table 4.2
n Pn n Pn n Pn
1 43 11 173 26 743
12 197 27 797
2 47 13 223 28 853
3 53 14 251 29 911
15 281 30 971
4 61 16 313 31 1033
5 71 17 347 32 1097
18 383 33 1163
6 83 19 421 34 1231
7 97 20 461 35 1301
36 1373
8 113 21 503 37 1447
9 131 22 547 38 1523
23 593
10 151 24 641 39 1601
25 691
Just because a rule, pattern or formula seems to work for several values of n, we
cannot simply conclude that it is valid for all values of n without going through a
legitimate proof.
How to Legalize a Pattern?
One way to legalize the pattern is to use the principle of Mathematical
induction. To see what it is, let us return to our question in the beginning of the
90 chapter. What is the sum of first n odd natural numbers?
, We have already seen that the formula Mathematical
Induction
Sn = 1 + 3 + 5 + ... + (2n – 1) = n2 is valid for n= 1, 2, 3, ..., 10 (1)
Do we need to compute Sn by adding the first n odd natural numbers ?
A moment’s reflection will show that it is not necessary.
Having obtained the value of Sn for some integer n, we can obtain the value of
Sn+1 = Sn + 2n + 1
if Sn = n2 for some n, then Sn+1 = Sn + 2n + 1 = n2 +2n+1 = (n+1)2.
That is, if Sn = n2 for some natural number n, then the formula holds for the next
natural number n + 1.
Since the formula Sn = n2 holds for n = 10, therefore it must hold n = 11. Since,
it holds for n = 11, therefore, it must hold for n = 12. Since, it holds for n = 12,
it holds for n = 13, and so on. The principle underlying the foregoing argument is
nothing but the principle of mathematical induction. We state this formally in
section 4.3.
4.1 OBJECTIVES
After studying this unit, you should be able to:
use the principle of mathematical induction to establish truth of several
formulae and inequalities for each natural number n.
4.2 THE PRINCIPLE OF MATHEMATICAL INDUCTION
Let Pn be a statement involving the natural number n. If
1. P1 is true, and
2. the truth of Pk implies the truth of Pk+1, for every interger k, then Pn must be
true all natural numbers n.
In other words, to prove that a statement Pn holds for all natural numbers, we
must go through two steps; First, we must prove that P1 is ture. Second, we
must prove that Pk+1 is true whenever Pk is true.
CAUTION Just proving Pk+1 whenever Pk is true will not work.
An Analogue 91
