An example of Mathematical Induction
Let P(n) be the proposition : 1´2 + 2´3 + 2^2´4 + ¼ + 2^n^-^1 (n + 1) = 2^n (n) , where n is a positive integer. We would like to use Mathematical Induction to prove that P(n) is true for all positive integers n. (1) For P(1), L.H.S. = 1´2 = 2 R.H.S. = 2^1´1 = 2 \ L.H.S = R.H.S.. \ P(1) is true. (2) Assume P(k) is true for some positive integer k , i.e. 1´2 + 2´3 + 2^2´4 + ¼ + 2^k^-^1 (k + 1) = 2^k (k) ……. (1) (3) For P(k+1), 1´2 + 2´3 + 2^2´4 + ¼ + 2^k^-^1 (k + 1) + 2^k (k + 2) = 2^k (k) + 2^k (k + 2) , by (1) = 2^k (k + k + 2) = 2^k^+1 (k + 1) \ If P(k) is true, then P(k + 1) is true. \Using (1), (2) and (3), By the Principle of Mathematical Induction, P(n) is true for all positive integers n . i.e. 1´2 + 2´3 + 2^2´4 + ¼ + 2^n^-^1 (n + 1) = 2^n (n) for all positive integers n .	See note 1 & 2 See note 3 See note 4 See notes 5 & 6 See note 7 See note 8 See note 9 See note 9
Note 1: The parts written in blue colour can be omitted. The parts written in red colour are important and should be written in most cases. Note 2: P(n) is a proposition (or statement) and can only be true or false (but not both). Do not mix up with the concept of "function". Note 3: You must NOT write "P(1) = 1´2 = 2". Note 4: You must NOT write "n = 1 is true." Note 5: You must NOT write "Assume n = k is true.", "Let n = k" You must NOT write "P(k) = 1´2 + 2´3 + 2^2´4 + ¼ + 2^k^-1 (k + 1) = 2^k (k)" Note 6: (a) Here you must use "some". You must NOT use "all" or "any". (b) Here you must use "positive integer" or "natural number" You must NOT use "positive number" , "real number" ,"integer" or "constant". Note 7: Give a number to identify your inductive hypothesis so that you can refer to later on. Note 8: Show that you have used the inductive hypothesis. Note 9: You must NOT use "all integers" or "all real numbers". You may use "all positive integers" or "all natural numbers".