Principle of Mathematical Induction:
Often it becomes a difficult job to prove a mathematical statement by a direct method. In such a case, an indirect method, known as the method of mathematical induction is used. This is a special technique to prove a mathematical statement involving a variable n, usually denoting a positive integer, in three steps. The steps are-
Verification Step- At this stage, the mathematical statement is verified to be true for the smallest permissible value of n.
Assumption Step- Here, the statement is assumed to be true for n = m, where m is any positive integer greater than the permissible lowest value of n.
Induction Step- This may also be referred to as the concluding step where the statement, which has been assumed to be true for n = m, is shown to be true for n = m + 1 only.
Now, as the statement has already been verified for n = 1 (or for the lowest permissible value of n), following the induction step, it will be true for n = 2 and so on. Thus, logically the statement is proved to be true for any value of n.
Hence, the principle of mathematical induction states that “If P(n) be a statement such that P(1) is verified to be true and P(m + 1) is true whenever P(m) is true, m being a positive integer, then the statement is true for all positive integral values of n.
| Example- Use the principle of mathematical induction to prove the validity of the following statements for all n ∈ N. (a) n2 + n is an even number. Solution- Let P(n) be the statement “n2 + n is an even number”. Put n = 1 P(1) = (1)2 + 1 = 2 = an even number ∴ P(n) is true for n = 1. Suppose P(n) is true for n = k i.e. k2 + k is an even number. Let k2 + k = 2λ ⇒ k2 = 2λ – k ………..(i) Now, we have to show that P(k+1) is true whenever P(k) is true i.e. we have to show that (k + 1)2 + (k + 1) is an even number. ∴ (k + 1)2 + (k + 1) = k2 +2k + 1 + k + 1 = k2 + 3k + 2 = 2λ – k + 3k + 2 [using (i)] = 2λ + 2k + 2 = 2 [λ + k + 1] = 2μ, μ ∈ N = an even number Therefore, P (k + 1) is true whenever P(k) is true. Hence by the principle of mathematical induction, P(n) is true if n ∈ N. (b) 10n + 3×4n+2 + 5 is divisible by 9. Solution- Let P(n) be the statement “10n + 3×4n+2 + 5 is divisible by 9″. Put n = 1 P(1) = 101 + 3×41+2 + 5 = 10 + 192 + 5 = 207 = 9 x 23 = divisible by 9 ∴ P(n) is true for n = 1. Suppose P(n) is true for n = k i.e. 10k + 3×4k+2 + 5 is divisible by 9. Let 10k + 3×4k+2 + 5 = 9λ ⇒ 10k = 9λ – 3×4k+2 – 5 …………(i) Now, we have to show that P(k+1) is true whenever P(k) is true i.e. we have to show that 10k+1 + 3×4(k+1) + 2 + 5 is divisible by 9. ∴ 10k+1 + 3×4(k+1) + 2 + 5 = 10k . 10 + 3×4(k+2) . 41 + 5 = (9λ – 3×4k+2 – 5) 10 + 12×4k+2 + 5 = 90λ – 30×4k+2 -50 + 12×4k+2 + 5 = 90λ – 18×4k+2 -45 = 9 (10λ – 2×4k+2 – 5) = 9μ is divisible by 9 Therefore, P (k + 1) is true whenever P(k) is true. Hence by the principle of mathematical induction, P(n) is true if n ∈ N. |
