MathsTips.com

Maths Help, Free Tutorials And Useful Mathematics Resources

  • Home
  • Algebra
    • Matrices
  • Geometry
  • Trigonometry
  • Calculus
  • Business Maths
  • Arithmetic
  • Statistics
Home » Algebra » Mathematical Induction

Mathematical Induction

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. (x+2) is a factor of x^2-3x+2
  3. Sum of first n natural numbers is \dfrac{n(n+1)}{2}
  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. n(n+1) is divisible by 2.
  2. 3^{2n}-1 is divisible by 8.
  3. n^2-n+41 is a prime integer.
  4. If a set S contains n distinct objects, then the number of subsets of S is 2^n .

All these statements are concerned with the natural number ‘n ’, which takes values 1, 2, 3, …etc. Such statements are usually denoted by P(n) or S(n) etc. By giving particular values to n , we get a particular statement. For example, if the statement “2^{3n}-1 is divisible by 7” is denoted by P(n) , then P(2) is the statement “2^{(3 \times 2)}-1 is divisible by 7”.

Principle of Mathematical Induction:

Let P(n) be a statement involving the natural number n , then P(n) is true \forall natural numbers n if

  1.  P(1) is true.
  2.  P(m+1) is true whenever P(m) is true.

In other words, to prove that a statement P(n) is true \forall natural numbers n, we have to go through two steps:

  1.  Verify the result for n=1 .
  2.  Assume the result to be true for n=m and prove the result for n=m+1 .

Illustrative Examples:

Example 1: Let P(n) be the statement “2^{3n}-1 is divisible by 7”. Prove that if P(m) is true then P(m+1) is also true.

Solution:

Given statement P(n) is “2^{3n}-1 is divisible by 7”.

Let P(m) be true

\Rightarrow 2^{3m}-1 is divisible by 7

\Rightarrow 2^{3m}-1=7\lambda , for some integer \lambda .

\Rightarrow 2^{3m}=1+7\lambda

2^{3(m+1)}-1 \\    = 2^{3m} \times 2^3-1 \\    = (1+7 \lambda) \times 8-1 \\    = 8+56 \lambda -1 \\    =7+56 \lambda

=7(1+8 \lambda) , which is divisible by 7

So, P(m+1) is true.

Example 2: Prove by mathematical induction that 1+3+...+(2n-1)=n^2 \forall n \in \mathbb{N} .

Solution:

Let P(n) be the statement

1+3+5+...+(2n-1)=n^2

Now P(1) means 1=1^2  i.e. 1=1 , which is true.

\Rightarrow P(1) is true.

Let P(m) be true i.e. 1+3+5+...+(2m-1)=m^2

For P(m+1) there are 1+3+5+ …upto (m+1) terms

For P(m+1): 1+3+5+...+(2(m+1)-1)

=1+3+5+...+ (2m+1) \\    = [1+3+5+...+ (2m-1)]+(2m+1) \\    =m^2+ (2m+1) \\    =m^2+2m+1 \\    = (m+1)^2

\Rightarrow P(m+1) is true.

Hence, by principle of mathematical induction, P(n) is true \forall n \in \mathbb{N} .

Example 3: Use principle of mathematical induction to prove that

3.2^2+3^2.2^3+3^3.2^4+...+3^n.2^(n+1)= \dfrac {12(6^n-1)}{5} \forall n \in \mathbb{N}

Solution:

Let P(n) be the statement “3.2^2+3^2.2^3+3^3.2^4+...+3^n.2^{(n+1)}= \dfrac{12(6^n-1)}{5} ”

Now P(1) means 3.2^2= \dfrac{12(6^1-1)}{5} i.e. 12=\dfrac{12 \times 5}{5} or, 12=12 , which is true.

\Rightarrow P(1) is true.

Let P(m) be true.

i.e. 3.2^2+3^2.2^3+3^3.2^4+...+3^m.2^{(m+1)}=\dfrac{12(6^m-1)}{5}

For P(m+1): 3.2^2+3^2.2^3+3^3.2^4+...+3^{(m+1)}.2^{(m+1)+1}

=3.2^2+3^2.2^3+3^3.2^4+ ... +3^m.2^{(m+1)}+3^{(m+1)}.2^{(m+2)}

=\dfrac{12.(6^m-1)}{5}+3^{(m+1)}.2^{(m+1)}.2

=\dfrac{2}{5}.6.6^m-\dfrac{12}{5}+(3.2)^{(m+1)}.2

=\dfrac{2}{5}.6^{(m+1)}-\dfrac{12}{5}+2.6^{(m+1)}

=[\dfrac{2}{5}+2].6^{(m+1)}-\dfrac{12}{5}

=\dfrac{12}{5}.6^{(m+1)}-\dfrac{12}{5}

=\dfrac{12}{5}[6^{(m+1)}-1]

\Rightarrow P(m+1) is true.

Hence, by principle of mathematical induction, P(n) is true \forall n \in \mathbb{N}

Example 4: Prove that 5^n-5 is divisible by 4 \forall n \in \mathbb{N} . Hence prove that 2.7^n+3.5^n-5 is divisible by 24 \forall n \in \mathbb{N}

Solution:

To prove that 5^n-5 is divisible by 4 \forall n \in \mathbb{N}

Let P(n) be the statement  5^n-5 is divisible by 4.

Now P(1) means 5^1-5 is divisible by 4 i.e. 0 is divisible by 4, which is true.

\Rightarrow P(1) is true.

Let P(m) be true i.e. 5^m-5 is divisible by 4

\Rightarrow 5^m-5=4\lambda , for some integer \lambda

\Rightarrow 5^m=4\lambda+5

For P(m+1): 5^(m+1)-5=5.5^m-5=5(4\lambda+5)-5

=20\lambda+20=4(5\lambda+5), which is divisible by 4

\Rightarrow P(m+1) is true.

Hence P(n) is true i.e. 5^n-5 is divisible by 4 \forall n \in \mathbb{N} .

To prove that 2.7^n+3.5^n-5 is divisible by 24, let P(n) be the statement “2.7^n+3.5^n-5 is divisible by 24”.

Here P(1) means 2.7^1+3.5^1-5 is divisible by 24

i.e. 14+15-5 is divisible by 24 i.e. 24 is divisible by 24, which is true

\Rightarrow P(1) is true.

Let P(m) be true i.e. 2.7^m+3.5^m-5 is divisible by 24

\Rightarrow 2.7^m+3.5^m-5=24q , for some integer q

\Rightarrow 2.7^m=24q-3.5^m+5

For P(m+1): 2.7^{(m+1)}+3.5^{(m+1)}-5=2.7^m.7+3.5.5^m-5

=7(24q-3.5^m+5)+15.5^m-5 \\    =168q-21.5^m+35+15.5^m-5 \\    =168q-6.5^m+30 \\    =168q-6(5^m-5) \\    =168q-6.4k

(\because 5^m-5 is divisible by 4,

\therefore 5^m-5=4k for some integer  k )

=24(7q-k) =24r , which is divisible by 24

(\because q,k are both integers

\therefore 7q-k is an integer, let 7q-k=r )

\Rightarrow P(m+1) is true.

Hence, 2.7^n+3.5^n-5 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 (2k+1) where k is a natural number. Then we have to prove that (2k+1)^2n=8q+1 where n,q \in \mathbb{N}

i.e. (2k+1)^2n-1 is divisible by 8.

Let P(n) be the statement “(2k+1)^2n-1 is divisible by 8″.

For n=1 , (2k+1)^2.1-1=(2k+1)^2-1=4k^2+4k+1-1=4k(k+1) .

k(k+1) being the product of two consecutive natural numbers, k(k+1) is always even.

Let k(k+1)=2p , where p \in \mathbb{N} .

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

\Rightarrow (2k+1)^2.1-1 is divisible by 8

\Rightarrow P(1) is true.

Let P(m) be true

i.e. (2k+1)^2m-1 is divisible by 8

\Rightarrow (2k+1)^2m-1=8q where q \in \mathbb{N}

\Rightarrow (2k+1)^2m=8q+1

For P(m+1): (2k+1)^2(m+1)-1=(2k+1)^2m.(2k+1)^2-1

=(8q+1)(8p+1)-1

=64pq+8p+8q

=8(8pq+p+q) , which is divisible by 8.

\Rightarrow P(m+1) 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 “n^2+n 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 \forall n \in \mathbb{N}
    1.  1+2+3+...+n= \dfrac{n(n+1)}{2} .
    2.  1^2+3^2+5^2+ … upto n terms =\dfrac{n(4n^2-1)}{3} .
    3.  10^(2n-1)+1 is divisible by 11.
    4.  3^(2n+2)-8n-9 is a multiple of 64.
    5.  (x-1) is a factor of x^(2n-1)-1 , where x \neq 1 .
    6.  a+(a+d)+(a+2d)+ upto n terms =\dfrac{n}{2}[2a+(n-1)d] .
    7.  7^n-3^n is divisible by 4.
    8.  Prove, by induction, that 5^(n+1)+4.6^n when divided by 20 leaves the remainder 9 \forall n \in \mathbb{N} .
« Simultaneous Equations
Different Type of Sets »


Filed Under: Algebra Tagged With: mathematical induction

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Table of Content

  • Complex Numbers
  • Quadratic Equations
  • Logarithm
  • Permutation
  • Combination
  • More on Complex Numbers
  • Classification of Numbers
  • Positive and Negative Quantities
  • Understanding Simple Algebraic Formulas With Examples
  • Integers
  • Linear Inequalities
  • An Introduction to Fundamental Algebra
  • Basic Number Properties – Commutative, Associative and Distributive
  • Algebraic Multiplication and Division
  • Simple Equations in One Variable
  • Simple Formulae and their Application
  • Rational and Irrational Numbers
  • Problems Leading to Simple Equations
  • Simultaneous Equations
  • Mathematical Induction
  • Different Type of Sets
  • Indices
  • Framing Formulas
  • Sequences
  • Introduction to Matrices
  • Addition Of Matrices
  • Subtraction Of Matrix
  • Multiplication of Matrices
  • Determinant of Matrices
  • Co-factor of Matrices
  • Minor of Matrices
  • Transpose and Adjoint of Matrices
  • Inverse of a Matrix
  • System of Linear Equations in Matrices
  • Introduction to Polynomials
  • Classification of Polynomials
  • Addition and Subtraction of Polynomials
  • Multiplication of Polynomials
  • Factoring Polynomials
  • Zeroes of Polynomial
  • Remainder Theorem of Polynomials
  • Factor Theorem of Polynomial
  • Simplifying Polynomial Fractions
  • Roots of a Polynomial
  • Addition of Polynomial Fractions
  • Subtraction of Polynomial Fractions
  • Multiplying polynomial fractions
  • Division of Polynomial Fractions

© MathsTips.com 2013 - 2023. All Rights Reserved.