Mathematical Induction PDF

# Chapter 1 Mathematical Induction ## Chapter Outline - 1.1 Summation Notation - 1.2 Principle of Mathematical Induction - 1.3 Performing Proofs by Mathematical Induction ## 1.1 Summation Notation ### Section Objective - Recognize the summation notation **Sigma (Σ)** * is a Greek letter and...

# Chapter 1 Mathematical Induction ## Chapter Outline - 1.1 Summation Notation - 1.2 Principle of Mathematical Induction - 1.3 Performing Proofs by Mathematical Induction ## 1.1 Summation Notation ### Section Objective - Recognize the summation notation **Sigma (Σ)** * is a Greek letter and read as 'sigma'. **Summation Notation** The symbol 'Σ' is often used to represent the sum of the terms of a sequence. For example, the summation notation ∑T is used to express the sum of T1, T2, T3 and T4. * i.e. ∑T = T₁ + T₂ + T₃ + T₄. Similarly, the sum of T3, T4, T5 and T6 can be expressed as ∑T. * i.e. ∑T = T3 + T₄ + T₅ + T₆. **Definition 1.1** If m and n are integers and m ≤ n, then ∑a = am + am+1 + am+2 + ... + an **Note:** The variable _r_ in ∑a can be replaced by other variables _i_, _j_, etc., i.e. ∑a = ∑a = ∑a. The variables _r_, _i_ and _j_ are called *dummy variables*. ## 1.2 Principle of Mathematical Induction ### Section Objectives - Understand the meaning of proposition - Understand the principle of mathematical induction - Point out that the principle can be applied only if both conditions of mathematical induction are satisfied. **Proposition** In mathematics, a proposition is a statement which is either true or false. **Principle of Mathematical Induction** A proposition P(n) is true for all positive integers n if both of the following conditions are satisfied: 1. P(1) is true. 2. Assume that P(k) is true for some positive integer k, then P(k + 1) is also true. **Caution** If the conditions (1) and (II) are not both satisfied, the proposition P(n) may not be true for all positive integers n. **The mechanism of mathematical induction works as follows:** P(1) is true. — Condition (I) Since P(1) is true, P(2) is also true. — Condition (II) Since P(2) is true, P(3) is also true. — Conidition (II) Since P(k) is true, P(k+1) is also true. — Condition (II) Using condition (II) repeatedly, it follows that P(n) is true for all positive integers n. **The idea of mathematical induction can also be illustrated by dominoes in a straight line.** If the 1st domino is pushed down and the fall of the kth domino causes the (k+1)th domino to fall down, all dominoes fall down successively. ## 1.3 Performing Proofs by Mathematical Induction ### Section Objective Prove propositions involving summation of a finite sequence by mathematical induction. **Example 1.4** Prove, by mathematical induction, that for all positive integers n, 1+2+3+...+n = n(n+1)/2. **Proof** Let P(n) be '1+2+3...+n=n(n+1)/2'. For n = 1, L.H.S. = 1 R.H.S. = 1 x (1+1)/2 = 1 L.H.S. = R.H.S. Therefore, P(1) is true. Assume that P(k) is true for some positive integer k. i.e. 1+2+3+...+k=k(k+1)/2 For n = k + 1, L.H.S. = 1+2+3+...+k+(k+1) = k(k+1)/2+(k+1) = (k+1)(k+1)/2 = (k+1)(k+2)/2 R.H.S. = (k+1)(k+2)/2 Therefore, P(k+1) is true if P(k) is true. By the principle of mathematical induction, P(n) is true for all positive integers n. **Note:** The variables _L.H.S._ and _R.H.S._ stand for Left-Hand Side and Right-Hand Side respectively.