Education Journalist | Study Abroad Lead
Mathematical induction is commonly a mathematical proof technique. It is a specialized form for working on different cases along with observations. Deductive Reasoning is one of the key basis for mathematical thinking. Induction is a method for drawing conclusions based on facts. This is a method which is used to determine the integrity for a wide variety of assertions in which analysis is done.
Read More: Binomial Theorem
| Table of Content |
Key Terms: Mathematical Induction, Statement, Motivation, Deduction, Inductive Hypothesis, Sum Formula, Recurrence Formula.
What is Mathematical Induction?
[Click Here for Sample Questions]
Mathematical induction is the technique for proving certain things like any statement, formula, theorem which is thought to be true for every natural number N.
Let us understand this with an example.
Garima goes to a toy shop which has different varieties of toys. The colour of all the toys in that toy shop is red. She picks a toy and brings it home. Now if she picks up a ball then what colour is it? Is it too difficult to answer?
No, obviously the colour of the ball is red as every toy in that toy shop is red.
What did we just do here? We used the concept of logical reasoning to deduce the colour of the ball.
Read Also:
Principle of Mathematical Induction
[Click Here for Sample Questions]
If the first object is hit, the events that take place in succession (i.e. every object is hit) is the mathematical induction. Motivation is a basic principle to understand mathematical induction. In a similar way, if the first tile is pushed in a specific direction, all tiles will fall. To be perfectly sure it is important to know that;
- First tile falls, and
- Rest are the successors that obviously fall.
This is the underlying principle here.
In a similar way to this approach, the concept of mathematical thinking can be taken to obtain conclusions.
- 25 is a real number
- All the numbers lying on the real number line are known as real numbers
- All the real numbers greater than zero are positive real numbers
We can consider from the preceding facts that if the last two statements are true,
then the first one is naturally true.
Illustration:
Suppose if we wish to find the formula for the sum of positive integers 1, 2, 3, 4.....,n, that is, a formula which will give the value of 1 + 2 + 3 + 4 when n = 4, the value 1 + 2 + 3 + 4 + 5, when n = 5 and so on and suppose in some way we assume to believe that the formula 1 + 2 + 3+ 4+.....+ n = n (n+1) is the correct one.
How can this formula be proved?
We can verify the statement for positive integers of n, but it will not prove for all values of n. What is required for this kind of chain reaction is - once the formula for one positive integer is proven, the formula will automatically follow for the next positive integer and so on forever. The method of mathematical induction can be used to induce such a reaction.
The video below explains this:
Principle of Mathematical Induction Detailed Video Explanation:
Read Also:
Properties of Mathematical Induction
[Click Here for Sample Questions]
Some important properties of mathematical induction are as follows:
Statement: A statement which can be interpreted as either true or false is called a sentence. For Example;
- Sixteen is divisible by eight.
- Any number divisible by eight is an even number.
- Sixteen is an even number.
Here, statements 1 and 2 are true so using these statements, 3 is also true.
Deduction: It is a process in which a statement is to be proven, often called a theorem. Deduction is the application of a general case to the particular case.
Assume (i) there is a given assertion P(n) concerning the natural number n that is true for n = 1, i.e., P(1), and
(ii) If the statement is true for n = k (where k is some positive integer), then it is also true for n = k + 1, i.e. the truth of P(k) implies the truth of P (k+1).
Then, for all natural integers n, P(n) is true.
Property (i) is only the factual statement. The (ii) property is a conditional property.
If the proposition holds for n = k, it likewise holds for n = k + 1. The inductive step is referred to describe this process. This is called Inductive Hypothesis.
Below are the steps used to prove statements:
Step 1: Assume that the assertion is true for an initial value of n. We must show that the statement is true for the starting value of n in this case.
Step 2: Assume the statement is correct for any value of n, such as n = k. Prove that the above assertion is likewise true for n = k + 1.
We should start with satisfying the value n = 5, i.e. P, when the value of n is true for assertions like n > 5.
If the given assertion is true for n = k and satisfies the value n = k, it is likewise true for n = k+1.
Step 3: Finally, we must divide n = k + 1 into two parts: one portion is n = k (which we just proved in the second step), and the other part must be shown.
The base step of mathematical induction in the technique is proving the assertion for the starting value, and the remaining procedure is known as the inductive step.
Read Also: NCERT Solutions For Class 11 Mathematics Chapter 4: Principle of Mathematical Induction
Formulas in Mathematical Induction
[Click Here for Sample Questions]
The formulas used in mathematical induction are given below:
Sum Formula:
For any positive integer n, 1 + 2 +…+ n = n (n+1)/2
Recurrence Formula:
These formulas are difficult to derive, but are easy to prove once we have them.
Things to Remember
[Click Here for Sample Questions]
- Mathematical induction is a proof technique which is used to prove that a statement is true for every natural number.
- The two steps in mathematical induction are: Base case and Induction step.
- The hypothesis stating that a statement is true for a particular value of n, in the inductive step, is referred to as Inductive Hypothesis.
- Mathematical induction can be understood as a sequence of steps taking place in succession to an initial event.
- The two formulas used in mathematical induction are sum formula and recurrence formula.
Sample Questions
Ques. Prove for all n³1 that, 12 + 22 + 32 + 42 +…..+ n2 = n (n+1) (2n+1)/6 (5 Marks)
Ans. Let the given statement be P(n)
P(n) : 12 + 22 + 32 + 42 +…..+ n2 = n (n+1) (2n+1)/6
For n = 1 , P(1) = 1 (1+1) (2×1+1)/6 = 1×2×3/6 = 1, which is true.
Assume P(k) is true some positive integer k, i.e.
12 + 22 + 32 + 42 +…..+ k2 = k (k+1) (2k+1)/6
We shall now prove, P(k+1) is also true
(12 + 22 + 32 + 42 +…..+ k2 ) + (k+1)2
= k (k+1) (2k+1)/6 + (k+1)2
= k (k+1) (2k+1) + 6 (k+1)2/6
= (k+1) ( 2k2 + 7k + 6)/6
= (k+1) ( k + 1 +1) {2 (k+1) +1}/6
Thus, P (k+1) is true, whenever P(k) is true.
Ques. Prove 2n > n, for all positive integers n. (3 Marks)
Ans. Let P(n) : 2n > n
when n = 1, 2n > n.
Hence, P(1) is true.
Assume P(k) is true for any positive integer k, i.e. 2n > k
We shall now prove P(k+1) is true, whenever P(k) is true.
Multiplying both side of (1) by 2 , we can get
2k > 2k
i.e. 2k+1 > 2k = k + k > k + 1
Therefore , P (k+1) is true when P (k) is true.
Hence, by principle of mathematical induction, P(n) is true for every positive
integer n.
Ques. Prove that 1+ 3 +…+(2n-1) = n2 for n = 3 (3 Marks)
Ans. Let n = 3,
2n – 1 = (23) – 1 = 6 – 1 = 5
so, LHS = 1 + 3 + 5 = 9
RHS = 32 = 9
Now since LHS = RHS
So, 1+ 3 +…+ (2n-1) = n2 for n = 3
Ques. Prove, 2.7n + 3.5n – 5 is divisible by 24 for all n Î N (5 Marks)
Ans. Let this statement be defined as P(n);
P(n): 2.7n + 3.5n – 5 is divisible by 24
P(n) is true for n = 1, since this 2.7n + 3.5n – 5 is divisible by 24.
Assume P(k) is true,
i.e. 2.7n + 3.5n – 5 = 24q where q Î N ….(1)
Now, to prove P(k+1) is true when P(k) is true we have,
2.7k+1 + 3.5k+1 – 5 = 2.7k . 71 + 3.5k . 51 – 5
= 7 [2.7k + 3.5k – 5 – 3.5k + 5] + 3.5k . 5 - 5
= 7 [ 24q - 3.5k + 5] + 15.5k – 5
= 7 24q – 6.5k + 30
= 7 24q -6 (5k – 5)
= 7 24q - 6 (4p) [(5k – 5) it is multiple of 4 why]
= 7 24q – 24p
= 24 (7q – p)
= 24 r; r = 7q – p , it is a natural number .. (2)
RHS of (1) is divisible by 24.
Thus, P(k+1) is true when P(k) is true,
Hence, P(n) is true for all n Î N.
Ques. Prove the rule of exponents (ab)n = anbn by applying the principle of mathematical induction for every natural number. (3 Marks)
Ans. Let P(n) for the given statement is, P(n): (ab)n = anbn
P(n) is true for n = 1 since (ab)1 = a1b1
Let P(k) be true for (ab)k = akbk
We shall now prove that for P(k+1) is true whenever P(k) is true.
So, (ab)k+1 = (ab)k (ab)
= (ak bk) (ab)
= (ak. a1) (bk. b1) = ak+1 . bk+1
Therefore, P(k+1) is true whenever P(k) holds true.
Ques. Using the principle of mathematical induction, prove that 1² + 2² + 3² + ..... + n² = (1/6) {n(n + 1) (2n + 1} for all n ∈ N. (5 Marks)
Ans. Let the given statement be P(n). Then,
P(n): 1² + 2² + 3² + ..... +n² = (1/6){n(n + 1)(2n + 1)}.
Putting n =1 in the given statement, we get
LHS = 1² = 1 and RHS = (1/6) × 1 × 2 × (2 × 1 + 1) = 1.
Therefore, LHS = RHS.
Thus, P(1) is true.
Let P(k) be true. Then,
P(k): 1² + 2² + 3² + ..... + k² = (1/6) {k(k + 1)(2k + 1)}.
Now, 1² + 2² + 3² + ......... + k² + (k + 1)²
= (1/6) {k(k + 1)(2k + 1) + (k + 1)²
= (1/6) {(k + 1).(k (2k + 1) + 6(k + 1))}
= (1/6) {(k + 1) (2k² + 7k + 6})
= (1/6) {(k + 1) (k + 2) (2k + 3)}
= 1/6 {(k + 1) (k + 1 + 1) [2(k + 1) + 1]}
⇒ P(k + 1): 1² + 2² + 3² + ….. + k² + (k+1)²
= (1/6) {(k + 1) (k + 1 + 1) [2(k + 1) + 1]}
⇒ P(k + 1) is true, whenever P(k) is true.
Thus, P(1) is true and P(k+1) is true, whenever P(k) is true.
Hence, by the principle of mathematical induction, P(n) is true for all n ∈ N.
Ques. By using mathematical induction, prove that the given equation is true for all positive integers. 2 + 4 + 6 + …. + 2n = n (n+1) (3 Marks)
Ans. From the statement formula,
When n = 1 or P (1),
LHS = 2
RHS =1 × 2 = 2
So P (1) is true.
Now we assume that P(k) is true or 2 + 4 + 6 + …. + 2k = k (k + 1).
For P(k + 1),
LHS = 2 + 4 + 6 + …. + 2k + 2(k + 1)
= k (k + 1) + 2 (k + 1)
= (k + 1) (k + 2)
= (k + 1) ((k + 1) + 1) = RHS for P(k+1)
Now it is proved that P(k+1) is also true for the equation.
So, the given statement is true for all positive integers.
Ques. By induction, prove that 3n - 1 is divisible by 2 is true for all positive integers. (3 Marks)
Ans. When n = 1, P(1) = 31 - 1 = 2 which is divisible by 2.
So P(1) is true.
Now we assume that P(k) is true or 3k - 1 is divisible by 2.
When P(k + 1),
3k + 1 - 1 = 3k x 3 - 1 = 3k x 3 - 3 + 2 = 3 (3k - 1) + 2
As (3k - 1) and 2 both are divisible by 2, it is proved that divisible by 2 is true for all positive integers.
Related Links:
Chapter Related Links:
Comments