Mathematical Induction



In Mathematical Induction we will discuss to important properties namely the Principle of Mathematical Induction and the Well Ordering Principle for non-negative integers.

What is Mathematical Induction?

1 + 2 + 3 + 4 + ..… + n = {n(n + 1)}/2.

For all positive integers n.

We denote this mathematical statement by P(n). If n = 1, then we find that {1(1 + 1)}/2= 1.

Hence the above statement is true for n = 1.

Suppose n = 2. Then 1 + 2 = 3 and {2(2 + 1)}/2= 3. So we find that the statement is true for n = 2.

Thus, it is easy to verify that P(n) is true for n = 1, 2, 3 or 4. But it is impossible to verify that the above statement is true for all positive integers.

To prove that the above statement P(n) is true for all positive integers we generally follow a method of proof which is known as proof by the Principle of Mathematical Induction or simply proof by mathematical induction. For this we assume the following important property of integers.

Principle of Mathematical Induction:

Let P(n) be a mathematical statement about nonnegative integers n and n be a fixed nonnegative integer.

(1) Suppose P(n₀) is true i.e.. P(n) is true for n = n₀.

(2) Whenever k is an integer such that k ≥ n₀ and P(k) is true, then
P(k + 1) is true.

Then P(n) is true for all integers n ≥ n₀.

The above property of integers is also called First Principle of Mathematical Induction. We now show how to prove.

1 + 2 + 3 + …………..+ n = {n(n + 1)}/2 ,

for all integers n ≥ 1 by mathematical induction.

Let P(n) be the statement

1 + 2 + 3 + …………..+ n = {n(n + 1)}/2, for all integers n ≥ 1

For n = 1, 1 = 1(1 + 1)/2 holds. Hence P(1) is true. Let k be an integer such that k ≥ 1. Assume that P(k) is true. Now

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

                               = {k(k + 1}/)2 + (k + 1) (since P(k) is true)

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

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

                               = {(k + 1)(k + 2)}/2.

Thus we find that P(k + 1) is true. Hence by mathematical induction it follows that P(n) is true for all integers n ≥ 1.

We note that a proof by mathematical induction consists of three steps.

• Step 1. (Basis) Show that P(n₀) is true.

• Step 2. (Inductive hypothesis). Write the inductive hypothesis: Let k be an integer such that k ≥ n₀ and P(k) be true.

• Step 3. (Inductive step). Show that P(k + 1) is true.

We have an equivalent statement of the Principle of mathematical induction which is often very useful. This equivalent statement is called strong form of mathematical induction or Second principle of mathematical induction.


Second Principle of Mathematical Induction:

Let P(n) be a mathematical statement about nonnegative integers n and n₀ be a fixed nonnegative integer. Suppose P(n₀) is true. If for any integer k ≥ n₀ ‘P(n₀ + 1), P(n₀ + 2), …. ..,P(k) arc true implies that P(k + 1) is true’, then P(n) is true for all is n ≥ n₀. 

Once can prove that the First Principle of Mathematical Induction holds if and only if the Second Principle of Mathematical Induction holds. For this proof one can see any standard book on algebra. Let us now show some application of this principle. For this we consider Fibonacci sequence f₁, f₂, f₃, ....... , where f₁ = 1 ,f₂ = 1, and f₀ = f₀ + f₀ for n ≥ 3. 

Then

f₃ = f₁ + f₂ = I + 1 = 2, 

f₄ = f₂ + f₃₀ = 1 + 2 = 3, and so on. 

Example: In this example we prove by strong form of math induction that

fn ≥ un - 2 for n ≥ 3 where U = (1 + √5)/2

Proof.

Let P(n) be the statement

fn ≥ un - 2 for n ≥ 3 where u = (1 + √5)/2

Basis Step. For n = 3, we have u = (1 + + √5)/2 < 2 and f3 = 2 and hence f3 ≥ u3 - 2.

Indctive hypothesis:

Assume that P(n) is true for all n such that 3 ≤ n ≤ k. where k is a positive integer.

Inductive step. In this step we show that P(k + 1) is true. Now u = shows that (1 + √5)/2 shows that u is a solution of x2 - x - 1 = 0. Then u2 = u + 1. Hence

uk - 2 = u2.uk - 4

= (u + 1).uk - 4

= uk - 3 + uk - 4 ≤ fk - 1 + f k - 2 (by inductive hypothesis)

But fk - 1 + fk – 2 = fk for k ≥ 3. Hence fk ≥ uk - 2 . Hence from the second principle of induction it follows that fn ≥ un - 2 for all n ≥ 3.


Since the First Principle of Mathematical Induction and Second Principle of Mathematical Induction are equivalent, henceforth we shall write only Mathematical Induction.


We now state the Well Ordering Principle for nonnegative integers.

Well Ordering Principle:

Any nonempty subset of nonnegative integers has a least element. i.e.. if S is a nonempty set of nonnegative integers, then there exists a є S such that is n ≤ m for all m є S.

We now point out that either the principle of mathematical induction or the well ordering principle can be proved as a theorem, given the other principle and the properties of integers: in other words we can say that these two principles are equivalent. For the proof of this statement one can see any standard hook on algebra.


Mathematical Induction

Mathematical Induction

Problems on Principle of Mathematical Induction

Proof by Mathematical Induction

Induction Proof




11 and 12 Grade Math 

From Mathematical Induction to HOME PAGE


New! Comments

Have your say about what you just read! Leave me a comment in the box below. Ask a Question or Answer a Question.