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.

Mathematical Induction is a technique normally used in Algebra to prove a case is true for every natural numbers. In inductive reasoning inferences are established upon repetitive patterns of observed cases and predictions are made from the logic established from the previous cases. The basis of the technique mathematical induction can be understood easily from the chain reaction or domino effect. When dominoes are standing close, if first one is pushed to fall, others will also fall in like a chain reaction. 

What is Mathematical Induction? 

In a statement of infinite sequence if it is stated for n numbers, by induction method it is to be proved that for any natural number it is true. Mathematical Induction method of proving has two steps. First one is base step and second is step case or inductive step.

In base step the statement is to be proved for an initial value of natural numbers. Normally 0 or 1 is used to prove the statement. In inductive step first thing is to assume that the statement is true for kth  iteration, using this assumption second thing is to prove that it is true for (k+1)th iteration. So after the statement is established for above two steps, then it can be induced it is true for any iteration or all the numbers in the statement.  The assumption in the inductive step is termed as Induction Hypothesis.

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. 

The steps of mathematical induction can be explained by an example.

Statement property P (n)

1² + 2² + 3² + ……. + n² = \(\frac{n(n+1)(2n+1)}{6}\)

We need to prove that the above statement is true for all natural numbers or positive integers.

Base Step:

P(1) or when n = 1

From the given statement LHS (Left Hand Side)= 1² = 1

RHS (Right Hand Side) = \(\frac{1(1 + 1)(2 × 1 + 1)}{6}\) = \(\frac{2 × 3}{6}\) = \(\frac{65}{6}\) = 1

Hence LHS = RHS.

Inductive Step:

Assume that P (k) is true.

That is 1² + 2² + 3² + ……. + n² = \(\frac{n(n+1)(2n+1)}{6}\) (induction hypothesis)

Now we have to establish P(k + 1) is true by using the above assumption or prove that

1² + 2² + 3² + ……. + (k + 1)² = \(\frac{(k + 1)((k + 1)  + 1)(2(k + 1) + 1)}{6}\)

Now L.H.S. = 1² + 2² + 3² + ……. + (k + 1)²

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

= \(\frac{k(k + 1)(2k + 1)}{6}\)  + (k + 1)²  (by using the assumption)

= \(\frac{k(k + 1)(2k + 1) + 6(k + 1)^{2}}{6}\) 

= \(\frac{(k + 1)(k(2k + 1) + 6(k + 1))}{6}\)

= \(\frac{(k + 1)(2k^{2} + 7k + 6)}{6}\)

= \(\frac{(k + 1)(2k^{2} + 4k + 3k + 6)}{6}\)

= \(\frac{(k + 1)(k + 2)(2k + 3)}{6}\)

= \(\frac{(k + 1)((k + 1) + 1)(2(k + 1) + 1)}{6}\) = RHS

Now it is proved that P (k+1) is true.

From this example we can understand that how to use step wise mathematical induction.

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

f_n ≥ u^{n - 2} for n ≥ 3 where U = (1 + √5)/2

Proof.

Let P(n) be the statement

f_n ≥ u^{n - 2} for n ≥ 3 where u = (1 + √5)/2

Basis Step. For n = 3, we have u = (1 + + √5)/2 < 2 and f₃ = 2 and hence f₃ ≥ u^{3 - 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 x² - x - 1 = 0. Then u² = u + 1. Hence

u^{k - 2} = u².u^{k - 4}

= (u + 1).u^{k - 4}

= u^{k - 3} + u^{k - 4} ≤ f_{k - 1} + f _{k - 2} (by inductive hypothesis)

But f_{k - 1} + f_{k – 2} = f_k for k ≥ 3. Hence f_k ≥ u^{k - 2} . Hence from the second principle of induction it follows that f_n ≥ u^{n - 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.

Trace of an implicit inductive proof was found in 370 BC in Plato’s Permenides, after that in Euclid’s theory of infinite numbers of primes and cyclic method of Bhaskara. Mathematical Induction became well known when Swiss mathematician Jakob Bernoulli established induction hypothesis. In 19th century George Boole, Augustus de Morgan, Charles Sanders Peirce, Giuseppe Peano, and Richard Dedekind are the mathematicians who employed this method largely. Giovanni Vacca (1872 –1953) Italian mathematician who was assistant to Giuseppe Peano and historian of science Maurolycus in G.Vacca, are believed to be the first discoverer of mathematical induction (1909).

 Mathematical induction is used to prove general structures such as trees termed as Structural Induction. This structural induction is used in computer science like recursion. Also it is used for correctness proofs for programs in computer science.

Mathematical induction method is a form of deductive reasoning. Like for an example: the planets are moving around the sun. The earth is planet. From the above two statements it can be stated that the earth is moving around the sun.

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