Principle of Mathematical Induction: Let P be a property of positive integers such that: Basis Step: P (1) is true, and Inductive Step: if P (n) is true, then P (n + 1) is true. Then P (n) is true for all positive integers. Remark : The premise P (n) in the inductive step is called Induction Hypothesis. The validity of the Principle of Mathematical Induction is obvious. The basis step states that P (1) is true. Then the inductive step implies that P (2) is also true. By the inductive step again we see that P (3) is true, and so on. Consequently the property is true for all positive integers. Remark: In the basis step we may replace 1 with some other integer m. Then the conclusion is that the property is true for every integer n greater than or equal to m. Example: Prove that the sum of the n first odd positive integers is n2, i.e., 1 + 3 + 5 + + (2n ••• 1) — ‘n2. Answer : Let S(n) 1 + 3 + 5 + + (2n 1). We want to prove by induction that ‘ ••• — for every positive integer n, S(n) n2. ‘ Basis Step: If n 1 we have S(1) 12, so the property is true for 1. ‘ ‘ 1 ‘ 2. Inductive Step: Assume (Induction Hypothesis ) that the property is true for some positive integer n, i.e.: n2. We must prove that it is also true for n + 1, i.e., S(n + 1) (n + 1)2 . In fact: S(n) ‘ ‘ S(n + 1) 1 + 3 + 5 + + (2n + 1) S(n) + 2n + 1 . ‘ ••• ‘ But by induction hypothesis, S(n) n2, hence: ‘ S (n + 1) + 2n + 1 (n + 1)2 . ‘n2 ‘ This completes the induction, and shows that the property is true for all positive integers. Example : Prove that 2n + 1 for n ≤ 2m ≥ 3.
Principle of Mathematical Induction: Let P be a property of positive integers such that: Basis Step: P (1) is true, and Inductive Step: if P (n) is true, then P (n + 1) is true. Then P (n) is true for all positive integers. Remark : The premise P (n) in the inductive step is called Induction Hypothesis. The validity of the Principle of Mathematical Induction is obvious. The basis step states that P (1) is true. Then the inductive step implies that P (2) is also true. By the inductive step again we see that P (3) is true, and so on. Consequently the property is true for all positive integers. Remark: In the basis step we may replace 1 with some other integer m. Then the conclusion is that the property is true for every integer n greater than or equal to m. Example: Prove that the sum of the n first odd positive integers is n2, i.e., 1 + 3 + 5 + ••• + (2n — 1) ‘n2. Answer : Let S(n) ‘ 1 + 3 + 5 + ••• + (2n — 1). We want to prove by induction that for every positive integer n, S(n) ‘ n2. Basis Step: If n ‘ 1 we have S(1) ‘ 1 ‘ 12, so the property is true for 1. 2. Inductive Step: Assume (Induction Hypothesis ) that the property is true for some positive integer n, i.e.: S(n) ‘ n2. We must prove that it is also true for n + 1, i.e., S(n + 1) ‘ (n + 1)2 . In fact: S(n + 1) ‘ 1 + 3 + 5 + ••• + (2n + 1) ‘ S(n) + 2n + 1 . But by induction hypothesis, S(n) ‘ n2, hence: S (n + 1) ‘n2 + 2n + 1 ‘ (n + 1)2 . This completes the induction, and shows that the property is true for all positive integers. Example : Prove that 2n + 1 ≤ 2m for n ≥ 3.