Embedded Files
The Chemical Science
Principle of Mathematical Induction
Principle of Mathematical Induction
Mathematical induction is one of the techniques, which can be used to prove a variety of mathematical statements which are formulated in terms of n, where n is a positive integer.
Let P(n) be given statement involving the natural number n such that
(i) The statement is true for n = 1, i.e. P(1) is true.
(ii) If the statement is true for n = k (where k is a particular but arbitrary natural number), then the statement is also true for n = k + 1 i.e. truth of P(k) implies that the truth of P(k + 1). Then, P(n) is true for all natural numbers n.
Mathematical Induction is a technique of proving a statement, theorem or formula which is thought to be true, for each and every natural number n. By generalizing this in form of a principle which we would use to prove any mathematical statement is ‘Principle of Mathematical Induction‘.
For example: 13 +23 + 33 + ….. +n3 = (n(n+1) / 2)2, the statement is considered here as true for all the values of natural numbers.
Principle of Mathematical Induction Solution and Proof
Consider a statement P(n), where n is a natural number. Then to determine the validity of P(n) for every n, use the following principle:
Step 1: Check whether the given statement is true for n = 1.
Step 2: Assume that given statement P(n) is also true for n = k, where k is any positive integer.
Step 3: Prove that the result is true for P(k+1) for any positive integer k.
If the above-mentioned conditions are satisfied, then it can be concluded that P(n) is true for all n natural numbers.
Proof:
The first step of the principle is a factual statement and the second step is a conditional one. According to this if the given statement is true for some positive integer k only then it can be concluded that the statement P(n) is valid for n = k + 1.
This is also known as the inductive step and the assumption that P(n) is true for n=k is known as the inductive hypothesis.
Solved problems
Example 1: Prove that the sum of cubes of n natural numbers is equal to ( [n(n+1)]/2)2 for all n natural numbers.
Solution:
In the given statement we are asked to prove:
13+23+33+⋯+n3 = ( [n(n+1)]/2)2
Step 1: Now with the help of the principle of induction in Maths, let us check the validity of the given statement P(n) for n=1.
P(1)=( [1(1+1)]/2)2 = (2/2)2 = 12 =1 .
This is true.
Step 2: Now as the given statement is true for n=1, we shall move forward and try proving this for n=k, i.e.,
13+23+33+⋯+k3= ( [k(k+1)]/2)2 .
Step 3: Let us now try to establish that P(k+1) is also true.
Example 2: Show that 1 + 3 + 5 + … + (2n−1) = n2
Solution:
Step 1: Result is true for n = 1
That is 1 = (1)2 (True)
Step 2: Assume that result is true for n = k
1 + 3 + 5 + … + (2k−1) = k2
Step 3: Check for n = k + 1
i.e. 1 + 3 + 5 + … + (2(k+1)−1) = (k+1)2
We can write the above equation as,
1 + 3 + 5 + … + (2k−1) + (2(k+1)−1) = (k+1)2
Using step 2 result, we get
k2 + (2(k+1)−1) = (k+1)2
k2 + 2k + 2 −1 = (k+1)2
k2 + 2k + 1 = (k+1)2
(k+1)2 = (k+1)2
L.H.S. and R.H.S. are same.
So the result is true for n = k+1
By mathematical induction, the statement is true.
We see that the given statement is also true for n=k+1. Hence we can say that by the principle of mathematical induction this statement is valid for all natural numbers n.
Example 3:
Show that 22n-1 is divisible by 3 using the principles of mathematical induction.
To prove: 22n-1 is divisible by 3
Assume that the given statement be P(k)
Thus, the statement can be written as P(k) = 22n-1 is divisible by 3, for every natural number
Step 1: In step 1, assume n= 1, so that the given statement can be written as
P(1) = 22(1)-1 = 4-1 = 3. So 3 is divisible by 3. (i.e.3/3 = 1)
Step 2: Now, assume that P(n) is true for all the natural numbers, say k
Hence, the given statement can be written as
P(k) = 22k-1 is divisible by 3.
It means that 22k-1 = 3a (where a belongs to natural number)
Now, we need to prove the statement is true for n= k+1
Hence,
P(k+1) = 22(k+1)-1
P(k+1)= 22k+2-1
P(k+1)= 22k. 22 – 1
P(k+1)= (22k. 4)-1
P(k+1) =3.2k +(22k-1)
The above expression can be written as
P(k+1) =3.22k + 3a
Now, take 3 outside, we get
P(k+1) = 3(22k + a)= 3b, where “b” belongs to natural number
It is proved that p(k+1) holds true, whenever the statement P(k) is true.
Thus, 22n-1 is divisible by 3 is proved using the principles of mathematical induction
Google Sites
Report abuse