Page 23 - DMTH401_REAL ANALYSIS

Unit 1: Sets and Numbers

n(n 1) Notes
+
= 5050 for n = 100.
2
What do these statements have in common and what do they indicate? The answer is obvious
that each statement is valid for every natural number.
Thus to a great extent, a large number of theorems, formulas, results etc. whose statement
involves the phrase, “for every natural number n” are those for which an indirect proof is most
appropriate. In such indirect proofs, clearly a criterion giving a general approach is applied. One
such criterion is known as the criterion of Mathematical Induction. The principle of Mathematical
Induction is Stated (without proof) as follows:

Principle of Mathematical Induction

Suppose that, for each n  N, P (n) is a statement about the natural number n. Also, suppose that
(i) P(1) is true,

(ii) if P(n) is true, then P(n + 1) is also true.
Then P(n) is true for every n  N.
Let us illustrate this principle by an example:

n(n 1)
+
Example: The sum of the first n natural numbers is
2
Solution: In other words, we have to show that for each n  N,
n(n 1)
+
l + 2 + 3+ … + n =
2
S = 1 + 2 + 3 + … + n
n
n
= å k.
k 1
=
Let P(n) be the statement that
+
n(n 1)
S =
n
2
+
1(1 1)
We, then, have S = 1 and = 1. Hence P(1) is true.
2
i
This proves part (i) of the Principle of Mathematical Induction. Now for (ii), we have to verify
that if P(n) is true, then P(n + 1) is also true. For this, let us assume that P(n) is true and establish
that P(n + 1) is also true. Indeed, if we assume that
+
n(n 1)
S = ,
n 2
then we claim that
(n 1) (n + 2)
+
S =
n + 1 2
Indeed
S = 1 + 2 + 3 + … + n + (n + 1)
n + 1
= S + (n + l)
n

LOVELY PROFESSIONAL UNIVERSITY 17