Goseeko blog

# What is the principle of mathematical induction?

Mathematical induction is a mathematical technique is used to prove a statement, a theorem or a formula is true for every natural number.

An essential property of the set N = {1, 2, 3, …} of positive integers follows:

Principle of Mathematical Induction I: Let P be a proposition defined on the positive integers N; that is, P(n) is either true or false for each n ∈ N. Suppose P has the following two properties:

(i) P(1) is true.

(ii) P(k + 1) is true whenever P(k) is true.

Then P is true for every positive integer n ∈ N.

We shall not prove this principle. In fact, this principle is usually given as one of the axioms when N is developed axiomatically.

Principle of Mathematical Induction II: Let P be a proposition defined on the positive integers N such that:

(i) P(1) is true.

(ii) P(k) is true whenever P(j) is true for all 1 ≤ j < k.

Then P is true for every positive integer n ∈ N.

Note: Sometimes one wants to prove that a proposition P is true for the set of integers {a, a + 1, a + 2, a + 3, . . .} where a is any integer, possibly zero. This can be done by simply replacing 1 by a in either of the above Principles of Mathematical Induction.

The technique has two steps to prove any statement-

1. Base step (it proves that a statement is true for the initial value)

2. Inductive step (it proves that is the statement is true for n’th iteration then it is also true for  (n+1)’th iteration.

Example:

Sol. here for n = 1, 1 = 1²

Now let us assume that the statement is true for n = k

Hence we assume that is true.

Now we need to prove that-

So that which satisfies the second step.

Hence-

Example-2:Prove 1+2+…+n=n(n+1)/2 using a proof by induction

Sol.

Let n=1: 1 = 1(1+1)/2 = 1(2)/2 = 1 is true,

Step-1: Assume n=k holds: 1+2+…+k=k(k+1)/2

Show n=k+1 holds: 1+2+…+k+(k+1)=(k+1)((k+1)+1)/2

Substitute k with k+1 in the formula to get these lines. Notice that I write out what I want to prove.

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

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

=(k(k+1) + 2(k+1))/2 by 2/2=1 and distribution of division over addition

=(k+2)(k+1)/2 by distribution of multiplication over addition

=(k+1)(k+2)/2 by commutativity of multiplication.

Example-3: Prove the following by using the principle of mathematical induction for all n N-

Sol. Here, n = 1, which is true

Step-1: Assume n = k holds-

Now show n = k + 1 also holds-

Consider-

Which is also true for n = k + 1.

Hence proved.