MathsTips.com

Mathematical Induction

Maths Tutor

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.

Mathematical statement:

A statement involving mathematical relation or relations is called a mathematical statement.

Consider the statements:

  1. 6 is an even natural number.
  2. is a factor of
  3. Sum of first natural numbers is
  4. Kolkata is the capital of West Bengal.

Statement 1, 2 and 3 are mathematical statements.

Notation for mathematical statements:

Consider the mathematical statements:

  1. is divisible by 2.
  2. is divisible by 8.
  3. is a prime integer.
  4. 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

  1.   is true.
  2.  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:

  1.  Verify the result for .
  2.  Assume the result to be true for and prove the result for .

Illustrative Examples:

Example 1: Let be the statement “ is divisible by 7”. Prove that if is true then is also true.

Solution:

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 .

Solution:

Let be the statement

Now means  i.e. , which is true.

is true.

Let be true i.e.

For there are …upto terms

For

is true.

Hence, by principle of mathematical induction, is true .

Example 3: Use principle of mathematical induction to prove that

Solution:

Let be the statement “”

Now means i.e. or, , which is true.

is true.

Let be true.

i.e.

For

is true.

Hence, by principle of mathematical induction, is true

Example 4: Prove that is divisible by 4 . Hence prove that is divisible by 24

Solution:

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.

is true.

Let be true i.e. is divisible by 4

, for some integer

For

which is divisible by 4

is true.

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

is true.

Let be true i.e. is divisible by 24

, for some integer

For

( is divisible by 4,

for some integer  )

, which is divisible by 24

( are both integers

is an integer, let )

is true.

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.

Solution:

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 .

(2k+1)^2.1-1=4.2p=8p $

is divisible by 8

is true.

Let P(m) be true

i.e. is divisible by 8

where

For

, which is divisible by 8.

is true.

Hence, by mathematical induction, the given statement is universally true.

Exercise:

  1. If P(n) is the statement “n(n+1)(n+2) is divisible by 6”, then what is P(3)?
  2. If P(n) is the statement “ is an odd integer”. Show that if P(m) is true then P(m+1) is also true.
  3. Using the principle of mathematical induction prove that
    1.  .
    2.   … upto terms .
    3.   is divisible by 11.
    4.   is a multiple of 64.
    5.   is a factor of , where .
    6.   upto terms .
    7.   is divisible by 4.
    8.  Prove, by induction, that when divided by 20 leaves the remainder 9 .
Exit mobile version