## 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) n^{2} + n is an even number.Solution- Let P(n) be the statement “n^{2} + 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. k ^{2} + k is an even number.Let k ^{2} + k = 2λ⇒ k ^{2} = 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) = k ^{2} +2k + 1 + k + 1 = k ^{2} + 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) 10^{n} + 3×4^{n+2} + 5 is divisible by 9.Solution- Let P(n) be the statement “10^{n} + 3×4^{n+2} + 5 is divisible by 9″.Put n = 1 P(1) = 10 ^{1} + 3×4^{1+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. 10 ^{k} + 3×4^{k+2} + 5 is divisible by 9.Let 10 ^{k} + 3×4^{k+2} + 5 = 9λ⇒ 10 ^{k} = 9λ – 3×4^{k+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 10 ^{k+1} + 3×4^{(k+1) + 2} + 5 is divisible by 9.∴ 10 ^{k+1} + 3×4^{(k+1) + 2} + 5= 10 ^{k} . 10 + 3×4^{(k+2)} . 4^{1} + 5= (9λ – 3×4 ^{k+2} – 5) 10 + 12×4^{k+2} + 5= 90λ – 30×4 ^{k+2} -50 + 12×4^{k+2} + 5= 90λ – 18×4 ^{k+2} -45= 9 (10λ – 2×4 ^{k+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. |