Mathematical Induction - MathsTips.com

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:

6 is an even natural number.
$(x+2)$ is a factor of $x^2-3x+2$
Sum of first $n$ natural numbers is $\dfrac{n(n+1)}{2}$
Kolkata is the capital of West Bengal.

Statement 1, 2 and 3 are mathematical statements.

Notation for mathematical statements:

Consider the mathematical statements:

$n(n+1)$ is divisible by 2.
$3^{2n}-1$ is divisible by 8.
$n^2-n+41$ is a prime integer.
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

$P(1)$ is true.
$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:

Verify the result for $n=1$ .
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:

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 “ $n^2+n$ 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
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}$ .

Leave a Reply Cancel reply