Mathematical Induction Notes

MATHEMATICAL INDUCTION INTRODUCTION Mathematical induction is a specialized form of deductive reasoning used to prove a fact about all the elements in an infinite set by performing a finite number of steps. The process of drawing a valid general result from particular results is called the process of induction. The principle of mathematical induction is a mathematical process which is used to establish the validity of a general result involving natural numbers. STATEMENT A sentence is called a statement if it is either true or false but not both. For example, the sentence “Two plus five equals seven” is a statement because this sentence is true. A statement concerning the natural number ‘n’ is generally denoted by P(n). For example, if P(n) denotes the statement : “n(n + 1) is an even number,” then P(3) is the statement : “3(3 + 1) is an even number’’ and P(7) is the statement : “7(7 + 1) is an even number” etc. Here P(3) and P(7) are both true. PRINCIPLE OF MATHEMATICAL INDUCTION Theorem-I If P(n) is a statement depending upon n, then to prove P(n) by induction, we proceed as follows : (i) Verify the validity of P(n) for n = 1 (ii) Assume that P(n) is true for any positive integer m and then using it establish the validity of P(n) for n = m + 1. Then P(n) is true for each n N Theorem-II If P(n) is a statement depending upon n but beginning with any positive integer k, then to prove P(n) by Induction, we proceed as follows : (i) Verify the validity of P(n) for n = k. (ii) Assume that the P(n) is true for n = m k. Then using it establish the validity of P(n) for n = m + 1. Then P(n) is true for each n k SOME USEFUL RESULT BASED ON PRINCIPLE OF MATHEMATICAL INDUCTION For any natural number n (i) 1 + 2 + 3 + ..... + n = n = n(n  1) 2 (ii) 12 + 22 + 32 + .... + n2 = n2 = n(n  1)(2 n  1) 6 2  n(n  1)  (iii) 1 + 2 + 3 + ...... + n = n = (n) =    2  3 3 3 3 3 2 (iv) 2 + 4 + 6 + ..... + 2n = 2n = n(n + 1) (v) 1 + 3 + 5 + ..... + (2n –1) = (2n –1) = n2 (vi) xn – yn = (x – y) (xn–1 + xn–2 y + xn–3 y2 + ...... + xyn–2 + yn–1) (vii) xn + yn = (x + y) (xn–1 – xn–2 y + xn–3 y2 + ..... – xyn–2 + yn–1) when n is odd positive integer (i) Product of r successive integers is divisible by r! (ii) For x  y, xn – yn is divisible by (a) x + y, if n is even (b) x – y, if n is even or odd (iii) x + y is divisible by x + y, If n is odd n n (iv) For solving objective question related to natural numbers we find out the correct alternative by negative examination of this principle. If the given statement is P(n), then by putting n = 1, 2, 3 .... in P(n) we decide the correct answer. We also use the above formulae established by this principle to find the sum of n terms of a given series. For this we first express Tn as a polynomial in n and then for finding Sn, we put  before each term of this polynomial and then use above results of n, n2, n3 etc. (v) If a given statement P(n) is to be proved for n = m + 1, m + 2, m + 3............ for some m  N, then we are required to prove that P(m + 1) is true instead of proving P(1) is true. Ex. Find the sum of the terms in the nth bracket of the series (1) + (2 + 3 + 4) + (5 + 6 + 7 + 8 + 9) + ...... Sol. For n = 1, we have Sum of the terms in first bracket = 1 and, (n – 1)3 + n3 = (1 – 1)3 + 13 = 1 for n = 2, we have Sum of the terms in the second bracket = 2 + 3 + 4 = 9 and, (n – 1)3 + n3 = (2 – 1)3 + 23 = 1 + 8 = 9 Ex. By using P.M.I. prove that 10 n + 3.4 n+2 + 5 is divisible by 9, n  N. Sol. Given statement is true for n = 1 as 10 + 192 + 5 = 207 is divisible by 9. Let us assume that the result is true for n = k i.e. 10k + 3.4k+2 + 5 = 9, N. Now for n = k + 1 10 k+1 + 3.4k+3 + 5 = 10(9 – 3.4k+2 – 5) + 3.4k+3 + 5 = 90 – 288.4k – 45 which is divisible by 9. so the result is true for n = k + 1 so by P.M.I. the result is true for all n  N. MATHEMATICAL INDUCTION Ex . 1 k   , then for some n N, find An . If A =  0 1  Sol. We find that 1 k   A2 =  0 1  1 k  1 2k    =  0 1  0 1  1 2k  1 k  1    = A3 =  0 1  0 1  0 3k   1  Similarly So 1 A4 =  0 4k   , A5 = 1  1 An =  0 nk   1  1  0 5k  etc. 1  Ex. Let P(n) be the statement "7 divides (23n – 1)". What is P(n + 1) ? Sol. P(n + 1) is the statement “7 divides (23(n + 1) – 1)” Clearly P(n + 1) is obtained by replacing n by (n + 1) in P(n). Ex. If is an imaginary cube root of unity then value of the expression 1.(2 – ).(2 – 2) + 2.(3 –).(3 – 2) + ..... + (n – 1) (n – ) (n – 2) isn n Sol. Sum =  (n 1)[n 2  n( 2 ) 3 ] n 1  (n  1)(n  )(n  2 ) = n 2 [when n = 1, sum = 0] = (n – 1) (n2 + n + 1) = (n3 – 1) = n3 – 1 = Ex. 1 2 n (n + 1)2 – n 4 If x and y are any two distinct integers, then prove by mathematical induction that (x n – y n) is divisible by (x – y) for all n  N. Sol. Let P(n) be the statement given by P(n) : (xn – yn) is divisible by (x – y) Step-I P(1) : (x1 – y1) is divisible by (x – y)  x1 – y1 = (x – y) is divisible by (x – y)  P(1) is true Step-II Let P(m) be true, then (xm – ym) is divisible by (x – y)  (xm – ym) = (x – y) for some  Z .....(i) We shall now show that P(m + 1) is true. For this it is sufficient to show that (xm+1 – ym+1) is divisible by (x – y). Now xm+1 – ym+1 = xm+1 – xmy + xmy – ym+1 = xm (x – y) + y(xm – ym) = xm (x – y) + y(x – y) [Using (i)] = (x – y) (x + y) which is divisible by (x – y) m So P(m + 1) is true thus P(m) is true  P(m + 1) is true Hence by the principle of mathematical induction P(n) is true for all n  N i.e. (xn – yn) is divisible by (x – y) for all n  N Ex. Prove by the principle of mathematical induction that n < 2n for all n  N. Sol. Let P(n) be the statement given by P(n) : n < 2n Step-I P(1) : 1 < 21  1 < 21  P(1) is true Step-II Let P(m) be true, then m < 2m we shall now show that P(m + 1) is true for which we will have to prove that (m + 1) < 2 m + 1 Now P(m) is true  m < 2m  2m < 2.2m  m + 1  m + m < 2m + 1  (m + 1) < 2m + 1  P(m + 1) is true thus P(m) is true   2m < 2m+1  (m + m) < 2m + 1 [ 1  m  m + 1  m + m] P(m + 1) is true So by the principle of mathematical induction P(n) is true for all n  N i.e. n < 2n for all n  N MATHEMATICAL INDUCTION In an algebra, there are certain results that are formulated in terms of n, where n is a positive integer. Such results can be proved by specific technique, which is known as the principle of Mathematical Induction. 1. First Principle of Mathematical Induction Let P(n) be a statement involving natural number n. To prove statement P(n) is true for all natural number, we follow following process. (i) Prove that P(1) is true. (ii) Assume P(k) is true. (iii) Using (i) and (ii) prove that statement is true for n = k + 1,. i.e. P(k + 1) is true. This is first principle of Mathematical Induction. 2. Second Principle of Mathematical Induction In second principle of Mathematical Induction following steps are used. (i) Prove that P(1) is true. (ii) Assume P(n) is true for all natural numbers such that 2  n < k. (iii) Using (i) and (ii) prove that P(k + 1) is true.