In drawing mathematical or scientific conclusions, there are two basic processes of reasoning that are commonly used. These are induction or deduction-induction is the process of reasoning from particular to general and deduction is the process of reasoning from general to particular. Induction begins by observations, and from observations we arrive at some tentative conclusions, conjectures. A conjecture may be true or false. The principle of mathematical induction helps us in proving some of these conjectures which are true.
A statement involving mathematical relation or relations is called a mathematical statement.
Consider the statements:
- 6 is an even natural number.
- is a factor of
- Sum of first natural numbers is
- Kolkata is the capital of West Bengal.
Statement 1, 2 and 3 are mathematical statements.
Notation for mathematical statements:
Consider the mathematical statements:
- is divisible by 2.
- is divisible by 8.
- is a prime integer.
- If a set contains distinct objects, then the number of subsets of is .
All these statements are concerned with the natural number ‘’, which takes values 1, 2, 3, …etc. Such statements are usually denoted by or etc. By giving particular values to , we get a particular statement. For example, if the statement “ is divisible by 7” is denoted by , then is the statement “ is divisible by 7”.
Principle of Mathematical Induction:
Let be a statement involving the natural number , then is true natural numbers if
- is true.
- is true whenever is true.
In other words, to prove that a statement is true natural numbers n, we have to go through two steps:
- Verify the result for .
- Assume the result to be true for and prove the result for .
Example 1: Let be the statement “ is divisible by 7”. Prove that if is true then is also true.
Given statement is “ is divisible by 7”.
Let be true
is divisible by 7
, for some integer .
, which is divisible by 7
So, is true.
Example 2: Prove by mathematical induction that .
Let be the statement
Now means i.e. , which is true.
Let be true i.e.
For there are …upto terms
Hence, by principle of mathematical induction, is true .
Example 3: Use principle of mathematical induction to prove that
Let be the statement “”
Now means i.e. or, , which is true.
Let be true.
Hence, by principle of mathematical induction, is true
Example 4: Prove that is divisible by 4 . Hence prove that is divisible by 24
To prove that is divisible by 4
Let P(n) be the statement is divisible by 4.
Now P(1) means is divisible by 4 i.e. 0 is divisible by 4, which is true.
Let be true i.e. is divisible by 4
, for some integer
which is divisible by 4
Hence is true i.e. is divisible by 4 .
To prove that is divisible by 24, let be the statement “ is divisible by 24”.
Here means is divisible by 24
i.e. is divisible by 24 i.e. 24 is divisible by 24, which is true
Let be true i.e. is divisible by 24
, for some integer
( is divisible by 4,
for some integer )
, which is divisible by 24
( are both integers
is an integer, let )
Hence, is divisible by 24.
Example 5: Prove by the method of induction that every even power of every odd integer greater than 1 when divided by 8 leaves 1 as remainder.
As the first odd integer greater than 1 is 3, let any odd integer be chosen as where is a natural number. Then we have to prove that where
i.e. is divisible by 8.
Let be the statement “ is divisible by 8″.
For , .
being the product of two consecutive natural numbers, is always even.
Let , where .
is divisible by 8
Let P(m) be true
i.e. is divisible by 8
, which is divisible by 8.
Hence, by mathematical induction, the given statement is universally true.
- If P(n) is the statement “n(n+1)(n+2) is divisible by 6”, then what is P(3)?
- If P(n) is the statement “ is an odd integer”. Show that if P(m) is true then P(m+1) is also true.
- Using the principle of mathematical induction prove that
- … upto terms .
- is divisible by 11.
- is a multiple of 64.
- is a factor of , where .
- upto terms .
- is divisible by 4.
- Prove, by induction, that when divided by 20 leaves the remainder 9 .