Mathematical Induction
Branch: Linear Algebra
Introduction: Reasoning or drawing conclusions can be classified in two categories
Inductive Reasoning
Deductive Reasoning
When a person makes observations and on their basis reaches conclusions its called inductive reasoning. Deductive reasoning, proceeds from assumptions rather than experience. Usually by inductive reasoning, mathematical results are discovered and by deductive reasoning they are proved.
"Inductive Reasoning is logically true but may or may not be realistically true."
What does that mean ?
Let’s consider an example :
Statement 1 : Watermelon is a fruit. (Specific statement)
Statement 2 : The box is full of fruits. (Specific statement)
We try to draw conclusion from these two statements,
Conclusion : The box is full of watermelons. (General conclusion)
Here statements 1 and 2 is true but the conclusion drawn although logically true can be false if the box contain any other fruit apart from watermelons. So here the conclusion is logically true but not definitely true so this approach of reasoning from SPECIFIC to GENERAL is called as Inductive Reasoning.
"Deductive Reasoning is logically true and also realistically true i.e.deductive reasoning is always true."
What does that mean ?
Let’s consider an example :
Statement 1 : All watermelons are fruits. (General statement)
Statement 2 : All fruits have seeds. (General statement)
What conclusion we can draw from these statements?
Conclusion : Watermelons have seeds. (Specific conclusion)
Here statement 1 and 2 is true and the conclusion will also always be true, all watermelons have seeds. So this approach of reasoning from GENERAL to SPECIFIC is called as Deductive Reasoning.
Thus, inductive reasoning starts with specific cases and ends with a general statement about all such cases, whereas deductive reasoning starts with a general statement and ends with a specific case. Mathematical Induction that we are going to discuss here belongs to Inductive reasoning.
Unlike other concepts and methods, proof by mathematical induction is not the invention of a particular individual at a fixed moment. It is said that the principle of mathematical induction was known by the pythagoreans.
The french mathematician Blaise Pascal is credited with the origin of the principle of mathematical induction.
The name induction was used by the English mathematician John Wallis.Later the principle was employed to provide a proof of the binomial theorem.
De Morgan contributed many accomplishments in the field of mathematics on many different subjects. He was the first person to define and name “Mathematical Induction”.
Let us try to understand Mathematical Induction with an analogy of climbing a ladder.
How do we climb a ladder ?
To climb a ladder, we need to know two things. First, to be able to get onto some step of the ladder ( let’s say step number one). Secondly, suppose we are able to get onto a particular step then we can get onto the next one.
This way we know that if we can get onto first step or any step, we can go onto the next step and hence we can climb the ladder.
Now let us relate this example with mathematical induction.
Mathematical induction is a method to prove a statement indexed by natural numbers. If we are able to prove that the statement is true for n=1 and if it is assumed to be true for n=k (some natural number) then it is true for n=k+1 (next natural number).
This way we can prove that the mathematical statement is true for any natural number.
Definition of MATHEMATICAL INDUCTION :
To show that a propositional function P(n) is true for all n ∈ N, where N is the set of natural number follow these steps:
Basis Step: Verify that P(1) is true.
Inductive Step: Show that if P(k) is true for some integer k≥1, then P(k+1) is also true.
Theorem (The Principle Of Mathematical Induction) :
“ For each positive integer n , let P(n) be a statement. If
1 The statement is true for n=1, i.e., P(1) is true , and
2 If the statement is true for n = k (where k is some positive integer),then the statement is also true for n = k+1 , i.e., truth of P(k) implies the truth of P(k+1)
Then , P(n) is true for all natural number n.”
Proof:
To prove this theorem we will use the contradiction method.
So let us suppose that the theorem is not true. Then conditions (1) and (2) are satisfied but there exist some positive integers n for which P(n) is a false statement.
So let us consider a set which contains those positive integers for which the statement P(n) is false i.e.,
S = {n ∈ N : P(n) is false }
Now since S is a non empty subset of N,it follows by the well-ordering principle that S contains a least element ‘s’ -------(1)
Well-ordering principle states that ” Every nonempty subset S of the positive integers has a least element”
Now since P(1) is true , 1 ∉S (because P(1) is a true statement whereas S contains only false statement).
Thus s ≥2 and s-1 ∈ N (because s is a number greater then 2 and 2-1=1 and so on, implies that s-1 will be a natural number.)
Therefore,
s-1 ∉S (Because we have already mentioned that S contains a least element s therefore s-1 can not be part of set S as s-1 is smaller than s which contradicts the fact that s is a least element.)
Which implies that P(s-1) is a true statement.
Now by condition (2),
P(s-1) is true implies that P(s) is also true.
And so s ∉S.
Which contradicts to our assumption that s ∈ S.
Hence our assumption is false and therefore P(n) is true for all natural number n.
Mathematical Induction-Solved Examples
Mathematical Induction Example (1):
For all n ≥ 1 , prove that
1+2+3+ … +n = [n(n+1)]/2
Solution :
Let the given statement be P(n), i.e.,
P(n) : 1+2+3+ … +n = [n(n+1)]/2
Basic step:
Now we will prove that the statement P(n) is true for n=1.
So for n=1,
P(1) : 1 = [1(1+1)]/2
= 2/2
= 1
Which is true.
Induction Step:
Now let’s assume that the statement P(n) is true for n=k i.e.,
1+2+3+ … + k = [k(k+1)]/2 -------------(1)
We shall now prove that the statement P(n) is true for n = k+1.
So for n=k+1 ,
1+2+3+ … + k +(k+1) = (1+2+3+ … + k) + (k+1)
= ( [k(k+1)]/2 ) + (k+1) ------(Using equation (1))
= [k(k+1) + 2(k+1)] / 2
= [(k+1)(k+2)] / 2
Thus P(k+1) is true whenever P(k) is true.
Hence, from the principle of mathematical induction , the statement P(n) is true for all natural numbers n.
The analogy that I see everywhere and which is quite interesting, is to compare induction to dominoes (and I don’t mean the pizza thing :D) which are lined up.
If you have ever made a domino line you are familiar with the general idea behind mathematical induction.The domino effect is really a great analogy for proof by induction.
The inductive step ensures that “dominoes are placed closed to one another, such as if one falls, then the next one will fall as well”.
The base case ensures that “the first domino is indeed pushed”.No matter how many dominoes we put on the table, as long as these two conditions are satisfied we are sure that all the dominoes will fall.
Mathematical Induction Example (2):
For all n ≥ 1 , prove that
1·3 + 3·5 + 5·7 + … +(2n-1)·(2n+1) = [n(4n2+6n-1)]/3
Solution:
Let the given statement be P(n), i.e.,
P(n) : 1·3 + 3·5 + 5·7 + … +(2n-1)·(2n+1) = [n(4n2+6n-1)]/3
Basic step:
Now we will prove that the statement P(n) is true for n=1.
So for n=1,
P(1) :1·3 = 3 & [1(4·12 + 6·1 -1)]/3 = [4+6-1]/3 = 9/3 =3
Therefore the statement is true for n=1.
Induction Step:
Now let’s assume that the statement P(n) is true for n=k i.e.,
1·3 + 3·5 + 5·7 + … +(2k-1)·(2k+1) = [k(4k2+6k-1)]/3 ------------(1)
We shall now prove that the statement P(n) is true for n = k+1.
So for n=k+1 ,
1·3 + 3·5 + 5·7 + … +(2k-1)·(2k+1)+(2(k+1)-1)·(2(k+1)+1)
= [k(4k2+6k-1)]/3 + (2(k+1)-1)·(2(k+1)+1) ---------(using equation (1))
= [k(4k2+6k-1)]/3 + (2k+2-1)·(2k+2+1)
= [k(4k2+6k-1)]/3 + (2k+1)·(2k+3)
= [k(4k2+6k-1)]/3 + (4k2+8k+3)
= { [k(4k2+6k-1)] + 3(4k2+8k+3) } /3 ---------(By taking LCM)
= (4k3+6k2-k+12k2+24k+9) /3
= (4k3+18k2+23k+9) /3
It can be written as ,
= (4k3+14k2+9k+4k2+14k+9)/3
= [k(4k2+14k+9)+1(4k2+14k+9)]/3
= [(k+1)(4k2+14k+9)]/3
= (k+1)(4k2+8k+4+6k+6-1)/3
= (k+1)[4(k2+2k+1)+6(k+1)-1]/3
= (k+1)[4(k+1)2+6(k+1)-1]/3
∴ 1·3 + 3·5 + 5·7 + … +(2k-1)·(2k+1)+(2(k+1)-1)·(2(k+1)+1) = (k+1)[4(k+1)2+6(k+1)-1]/3
Thus P(k+1) is true whenever P(k) is true.
Hence, from the principle of mathematical induction, the statement P(n) is true for all natural numbers n.
Mathematical Induction Example (3):
For all n ≥ 1 , prove that
a+ ar+ ar2 +…+ arn-1 = a(rn-1)/r-1
Solution:
Let the given statement be P(n), i.e.,
P(n) : a+ ar+ ar2 +…+ arn-1 = a(rn-1)/r-1
Basic step:
Now we will prove that the statement P(n) is true for n=1.
So for n=1,
P(1) : a & a(r1-1)/(r-1)= a
Therefore the statement is true for n=1.
Induction Step:
Now let’s assume that the statement P(n) is true for n=k i.e.,
a+ ar+ ar2 +…+ ark-1 = a(rk-1)/r-1 --------------(1)
We shall now prove that the statement P(n) is true for n = k+1.
So for n=k+1 ,
a+ ar+ ar2 +…+ ark-1+ ar(k+1)-1 = ( a(rk-1)/r-1 ) + ark -----(by equation (1))
= [ a(rk-1) + (r-1) ark ] / (r-1) --(by taking LCM)
= [ark-a + ark+1 -ark] / (r-1)
= (ark+1 - a) / (r-1)
= a(rk+1- 1)/ (r-1)
∴ a+ ar+ ar2 +…+ ark-1+ ar(k+1)-1 = a(rk+1- 1)/ (r-1)
Thus P(k+1) is true whenever P(k) is true.
Hence, from the principle of mathematical induction , the statement P(n) is true for all natural numbers n.
Mathematical Induction Example (4):
For all n ≥ 1 , prove that n(n+1)(n+5) is a multiple of 3.
Solution:
Let the given statement be P(n), i.e.,
P (n): n (n + 1) (n + 5), which is a multiple of 3
Basic step:
Now we will prove that the statement P(n) is true for n=1.
So for n=1,
P(1) : 1 (1 + 1) (1 + 5) = 12, which is a multiple of 3.
Therefore the statement is true for n=1.
Induction Step:
Now let’s assume that the statement P(n) is true for n=k i.e.,
k (k + 1) (k + 5) is a multiple of 3
let,
k (k + 1) (k + 5) = 3m, where m ∈ N --------------(1)
We shall now prove that the statement P(n) is true for n = k+1.
So for n=k+1 ,
Here,
(k + 1) {(k + 1) + 1} {(k + 1) + 5}
We can write it as
= (k + 1) (k + 2) {(k + 5) + 1}
= (k + 2) (k+1) (k + 5) + (k + 1) (k + 2)
= {k (k + 1) (k + 5) + 2 (k + 1) (k + 5)} + (k + 1) (k + 2)
= k (k + 1) (k + 5) + {2 (k + 1) (k + 5) + (k + 1) (k + 2)}
= 3m + (k + 1) {2 (k + 5) + (k + 2)} -------(by using equation (1) )
= 3m + (k + 1) {2k + 10 + k + 2}
= 3m + (k + 1) (3k + 12)
= 3m + 3 (k + 1) (k + 4)
= 3 {m + (k + 1) (k + 4)}
= 3 × q where q = {m + (k + 1) (k + 4)} is some natural number
∴ (k + 1) {(k + 1) + 1} {(k + 1) + 5} is a multiple of 3
Thus P(k+1) is true whenever P(k) is true.
Hence, from the principle of mathematical induction , the statement P(n) is true for all natural numbers n.
Mathematical Induction Example (5):
For all n ≥ 1 , prove that 32n+2-8n-9 is divisible by 8.
Solution:
Let the given statement be P(n), i.e.,
P (n): 32n+2-8n-9 is divisible by 8.
Basic step:
Now we will prove that the statement P(n) is true for n=1.
P (1) = 32 × 1 + 2 – (8 × 1) – 9 = 64, which is divisible by 8
Therefore the statement is true for n=1.
Induction Step:
Now let’s assume that the statement P(n) is true for n=k i.e.,
32k+2 – 8k – 9 is divisible by 8
let,
32k + 2 – 8k – 9 = 8m, where m ∈ N -----------(1)
We shall now prove that the statement P(n) is true for n = k+1.
So for n=k+1 ,
32(k + 1) + 2 – 8 (k + 1) – 9 = 32k + 2 · 32 – 8k – 8 – 9
By adding and subtracting 8k and 9 we get
= 32 (32k + 2 – 8k – 9 + 8k + 9) – 8k – 17
= 32 (32k + 2 – 8k – 9) + 32 (8k + 9) – 8k – 17
= 9. 8m + 9 (8k + 9) – 8k – 17 ---(by equation (1))
= 9. 8m + 72k + 81 – 8k – 17
= 9. 8m + 64k + 64
= 8 (9m + 8k + 8)
= 8r, where r = (9m + 8k + 8) is a natural number
So 3 2(k + 1) + 2 – 8 (k + 1) – 9 is divisible by 8
Thus P(k+1) is true whenever P(k) is true.
Hence, from the principle of mathematical induction , the statement P(n) is true for all natural numbers n.
Mathematical Induction Questions
Q.1) 12 +22 +32 +…+n2 =(1/6)·n(n+1)(2n+1)
Q.2) 1/2 +1/4 +1/8 +…+1/2n = 1-(1/2n)
Q.3) 1/(3·5) + 1/(5·7) + 1/(7·9) +…+ 1/((2n+1)·(2n+3)) = n/(3·(2n+3))
Q.4) 32n-1 is divisible by 8.
Q.5) 34n+2 +52n+1 is a multiple of 14.
FAQs on Mathematical Induction
Q. What is meant by mathematical induction?
A. Mathematical Induction can be defined as the process of proving any theorem, statement or expresssion, with the help of a sequence of steps for all natural numbers.
Q. What is the Principle of Mathematical Induction?
A. The Principle of Mathematical Induction states that, " For each positive integer n, let P(n) be a statement, if the statement is true for n=1 and if the statement is true for n=k, where k is a positive integer, then the statement is also true for n = k+1, i.e if P(k) is true then P(k+1) is also true."
Q. Why do we use Mathematical Induction?
A. Mathematical Induction is basically used to prove that a given theorem, statement or expression holds true for all the natural numbers.
Q. What are the steps to solve a mathematical induction problem?
A. There are two main steps to solve a mathematical induction problem. The first step is to prove that P(1) is true and the second step is to prove that if P(k) is true, where k is a positive integer, then P(k+1) is also true. Then we can say that P(n) is true for all natural numbers.
Q. Which type of reasoning does Mathematical Induction belong to?
A. Mathematical Induction belongs to Inductive Reasoning, since the statement can be logically true but may or may not be realistically.