Principle of Mathematical Induction

Reasoning and deducing a conclusion form the basis of reasoning. Reasoning, in turn, leads to better inductions. When it comes to induction in mathematics, we intend to reach to proofs and conclusions that help us in the better understanding of theorems and examples. In the chapter below we shall learn about the various properties of mathematical inductions that form the basis of theoretical maths.

Suggested Videos

 

Introduction to Mathematical Induction

Mathematical thinking is essential, as it helps in better understanding of problems thus letting us reach to solutions in a better way. Deductive reasoning and mathematical thinking are connected, as the former forms the basis of the latter. Deductive reasoning further is based on logic and understanding. See the example given underneath:

1. The German shepherd is a dog.
2. All dogs have an immaculate sense of hearing.
3. The German shepherd has an immaculate sense of hearing.

Now, if statements a) and b) are true then c) is also true. This theory of reasoning can be used mathematically as well, let’s see how?

1. Sixteen is divisible by Two.
2. Any number divisible by two is an even number.
3. Sixteen is an even number.

From the above example, we get a hint of deduction.

The deduction is the statement that needs to be proven and is generally called a theorem in mathematics. With the help of deductive steps, we prove or disprove theorems also called as conjectures that let us establish mathematical facts and principles. In a nutshell, the deduction is the application of general cases to a particular case.

Inductive reasoning is the opposite of deductive reasoning. Inductive reasoning depends on the study of a particular case and observing incidences leading to that case. This implies that in inductive reasoning we observe each and every case that lets us reach conclusions for a particular case.

Reasoning through induction forms the basis of scientific reasoning and if generally used in mathematics. Since collecting and analyzing information is a norm in scientific reasoning, mathematical induction also uses the same norms to generalize particular facts or cases.

The principle of mathematical induction is used in algebra or other streams of mathematics that involve the formulation of results or statements in terms of “n”. To prove the basic principle behind ‘n’, which is a positive integer, we use a set of well-established and well-suited principles in a specific format. The techniques used to prove statements with regard to “n” are known as principles of mathematical induction.

Video on Mathematical Induction

The Principle of Mathematical Induction

As a mathematical technique of proving things, mathematical induction is essentially used to prove the property of natural numbers (n). According to the principle of mathematical induction, a property X(n) holds to be same for all natural numbers, 0,1,2,3…… n. Let’s consider a given statement X(n) involving natural number n, so that

1. The statement is true for n = 1 i.e., X(1) is true, and
2. If the statement is true for n=k, where k is a positive integer, then the statement is also true for all cases of
   n= k+1 i.e., X(k) leads to the truth of X(k+1).

This means that X(n) is true for all the natural numbers, n.

• Property a) mentioned above is simply a statement of a fact. In situations, where the statement is also true for all the cases of n≥5, then the step a) shall start from n=5 and we shall hence verify the result for n=5, i.e., X(5).
• Property b) is a conditional property as it does not confirm that the given statement is true for n=k, but if it is true for n=k then it shall also be true for n=k+1.

Therefore to prove a property we need to first prove the conditional proposition. Proving a conditional proposition is referred to as inductive step of a theorem. The presumption that the given statement, is true, in this case, n=k is termed as the inductive hypothesis.

You can download Principle of Mathematical Induction Cheat Sheet by clicking on the download button below

 

Example

Mathematics follows a pattern, one of the many patterns is given below

1 = 1² = 1
4 = 2²= 1 + 3
9 = 3² = 1 + 3 + 5
16 = 4² = 1 + 3 + 5 + 7
25 = 5² = 1 + 3 + 5 + 7 + 9

From the above pattern example, we come to a conclusion that the square of the second natural number is equal to the sum of first two odd natural numbers. Likewise, the sum of first three odd natural numbers is equal to the square of the third natural number. From the above pattern we conclude that,

1 + 3 + 5 + 7 + … + (2n – 1) = n² , or the square of n is equal to the sum of first n odd natural numbers. Now let us write this as,
X(n) = 1 + 3 + 5 + 7 + 9 +…….+ (2n-1) = n²

With the help of the principle of mathematical induction, we need to prove that X(n) is true for all the values of n. The first step in this process is to prove the value X(1) is true. This first step is called the base step or basic step, as it forms the basis of mathematical induction. 1 = 1² , X(1) therefore is true.

The next step following the base is called the inductive step. In this step we suppose that X(m) is true for any positive integer m, we also need to prove that X(m+1) is true. Since X(m) is true we have,

1 + 3 + 5 + 7…. + (2m-1) = m²                                                        (1)
Now consider, 1 + 3 + 5 + 7 +….+ (2m-1) + {2(m+1)-1}           (2)
Using (1), we get
= m² + (2m + 1) = (m + 1)²

Therefore, X(m + 1) is also true thus completing our inductive proof step. This gives us that X(n) is true for all the natural numbers. Through the above example, we have proved that X(n) is true for all natural numbers n.

Solved Example For You

Question: Prove that m≥ 1 prove that, 1²+ 2² + 3² +4² +……+ m² = m(m + 1)(2m + 1)/6

Solution: Let the given statement be X(m), i.e.,
X(m) = 1²+ 2² + 3² +4² +……+m² = m(m + 1) (2m + 1) / 6
for m= 1 , X(1) = 1(1 + 1) (2 × 1 + 1) /6
= 1 × 2 × 3 / 6 = 1, which is true.

Now, lets take a positive integer, p, and assume X(p) to be true i.e.,
1²+ 2² + 3² +4² +……+p² = p(p+1) (2p+1) / 6                      (1)
We shall now prove that X(p+1) is also true, so now we have,

1²+ 2² + 3² +4² +……+p²  + (p+1)²
= p(p+1)(2p+1) / 6 + (p+1)²
= p(p+1)(2p+1)+6(p+1)² / 6
= (p+1) {( 2p² + p) + 6(p+1)} /6
= (p+1) (2p² +7p+6)/6
= (p+1) (p+1+1) {2(p+1) +1 /6
Thus X(p + 1) is true, whenever X(p) is true for all natural numbers.

Ques. What does induction mean in math?

Ans. Induction in mathematics is a mathematical proof method that we use to prove a given statement about any well-organized set. Generally, we use it to establish statements for the set of all the natural numbers. The induction in mathematics is a form of direct proof, usually completed in 2 steps.

Ques. How do we prove by induction?

Ans. A proof through the induction is like a normal proof where every step must be justified. It employs a well-ordered trick that allows us to prove a statement for an arbitrary number ‘n’ by firstly proving it is true when the number ‘n’ is 1 and then assuming that it’s true for n = k and representing that it’s true for n = k + 1.

Ques. What is a weak induction?

Ans. In a weak induction process, we only assume that specific statement holds at the kth step, whereas in the strong induction we assume that the specific statement holds at every step from the base case to the kth step.

Ques. What is a perfect induction?

Ans. The process of proving a theorem by verifying all the combinations of the values that the variables may assume.