Principle of Mathematical Induction

Introduction to Mathematical Induction

The mathematical induction method is useful to prove any given axiom about any well-organized set. Usually, one can use it to verify results or establish statements formulated in terms of n, where n is a natural number. 

As stated below, the method involves a few steps given below to prove a statement, P(n):

• Verify that the statement is true for trivial cases, such as n = a, i.e. P(a) is correct. [Base Case]
• Assume the statement is true for n = k for some k > a, so then P(k) is correct. [Inductive Hypothesis]

The truth of P(k) implies the truth of P(k + 1), so the statement P(n) is true for all n ≥ a.

Together, the base step and inductive step prove that P(k) => P(k + 1) => P(k + 2) Therefore, P(n) is correct for each n ≥ a. 

Let us understand mathematical induction with the help of an example. Each domino knocks down the next one in succession after it falls. The first domino knocks down the second, the second knocks down the third, and so on. The dominoes will all be knocked over in the end.

However, some conditions have to be met that are the same as the steps of mathematical induction discussed earlier:

• The first domino must fall to begin the knocking process. This is the first step.

• Any two adjacent dominoes must have the same distance between them. If not, a domino may fall without knocking over the next. This would stop the sequence of reactions. Keeping the inter-domino distance equal ensures that P(k) ⇒ P(k + 1) for each integer k ≥ a. That is the inductive step.

Interesting Facts on Mathematical Induction

Unlike other concepts and methods, proof by mathematical induction was not invented by a particular person at a specific time. The Pythagoreans were said to have known the principle of mathematical induction. 

According to legend, Blaise Pascal is credited with originating the principle of mathematical induction. 

Induction was the name given to it by the English mathematician John Wallis. The principle was later used to prove the binomial theorem. 

De Morgan is credited with many accomplishments in mathematics in many subjects. It was he who defined and named “mathematical induction” as well as developed De Morgan’s rule to determine the convergence of a mathematical series.

1. Peano deduced the properties of natural numbers from a set of explicitly stated assumptions, known as his axioms. The principle of mathematical induction restates one of Peano’s axioms. 

Proof of Mathematical Induction

There is a given statement P(n) involving the natural number n such that

• It is true for n = 1, i.e., P(1) is true, and 
• If it is true for n = k (where k is some positive integer), then it must also be true for n = k + 1, i.e., the truth of P(k) implies the truth of P(k + 1). 

For all natural numbers n, P(n) is true. 

It is simply a statement of fact. In some cases, a statement may be true for n ≥ 4. In this case, step 1 will start from n = 4, and we will verify the result for n = 4, which is P(4). This is a conditional property. It does not assert that the given statement is true for n = k, but only that if it is true for n = k, then it is also true for n = k +1. 

To prove that the property holds, only demonstrate the conditional proposition: if the statement is true for n = k, then it is also true for n = k + 1. This step is sometimes referred to as induction. 

In this inductive step, the inductive hypothesis states that the given statement is true for n = k.

Sometimes in mathematics, a formula will be discovered that appears to follow a pattern such as

1 = 12 = 1

4 = 22 = 1+3

9 = 33 = 1+3+5

Note that the sum of the first two odd natural numbers is the square of the second natural number, the sum of the first three odd natural numbers is the square of the third natural number, and so on.

This pattern indicates that 1 + 3 + 5 + 7 + … (2n – 1) =n2, i.e., the sum of the first n odd numbers is the square of n. Let us write P(n) as follows: 1 + 3 + 5 + 7 + … + (2n – 1) = n2. 

A proof that uses mathematical induction must be true for all n. The first step in proving that P (1) is true is to prove that P (2) is true. This is the basic step. P(1), therefore, states that 1 = 1. 

Inductive reasoning is the next step. We assume P (k) is true for some  positive integer k, and we need to prove that P (k + 1) is true. Since P (k) is true, we have 1 + 3 + 5 + 7 + … + (2k – 1) = k2 … (1) 

Consider 1 + 3 + 5 + 7 + … + (2k – 1) + {2(k +1) – 1} … (2) 

= k2 + (2k + 1) = (k+1)2 [Using (1)] 

Therefore, P (k + 1) is true and the inductive proof is complete. 

P(n) is therefore true for all natural numbers n.

A statement about mathematics can be proven by mathematical induction n≥1.

The following steps are required.

• In the first step, verify the statement for validity, put n=1.
• For the inductive hypothesis, assume the statement holds when k=n
• n=k for some integer k≥1.
• In the inductive step, use the information gleaned from the inductive hypothesis to prove that the statement also holds when n=k+1. Make sure you complete all three steps.

• Take note of the wording. 

• Follow the template closely at the beginning. You can start venturing out on your own once you feel comfortable with the whole process.

Summary 

With these study notes on the principle of mathematical induction, you must have a clear idea of various concepts and formulae related to mathematical induction. Mathematical induction is one tool that can be used to prove a wide variety of mathematical statements. Each such statement is assumed to be P(n) associated with a positive integer n, for which the correctness is tested for the case n = 1. If the truth of P(k) is established for some positive integer k, then the truth of P (k+1) is established.