Induction

Definition of Induction

Mathematical Induction is a method generally used to prove or establish that a given statement is true for all natural numbers.

More About Induction

    It is a method to prove a proposition which is valid for infinitely many different values of a variable.

Video Examples: Mathematical Induction


Example of Induction

    Mathematical induction can be used to prove that 1 + 3 + 5 + ---- + (2n - 1) = n2 for all positive integers.
    Let Pn be the statement 1 + 3 + 5 + ---- + (2n - 1) = n2.
    P1 is true because (2(1) - 1) = 12.
    Assume that Pk is true, so that Pk: 1 + 3 + 5 + ------ + (2k - 1) = k2. [The Inductive Hypothesis.]
    The next term on the left hand side would be [2(k + 1) - 1] = (2k + 1). Add (2k + 1) on both sides to Pk.]
    1 + 3 + 5 + ------ + (2k - 1) + (2k + 1) = k2 + (2k + 1) = (k + 1)2 = Pk+1
    So, the equation is true for n = k + 1.
    Therefore, Pn is true for all positive integers, by mathematical induction.

Solved Example on Induction

Ques: Using mathematical induction to prove that 1 + 5 + 9 + ------ + (4n - 3) = n(2n - 1) for all positive integers.

Solution:

    Step 1: Let Pn be the statement 1 + 5 + 9 + ---- + (4n - 3) = n (2n - 1).
    Step 2: P1 is true because (4(1) - 3) = 1(2(1) - 1) [The Anchor.]
    Step 3: Assume that Pk is true, so that Pk: 1 + 5 + 9 + ---- + (4k - 3) = k (2k - 1) [The Inductive Hypothesis.]
    Step 4: The next term on the left-hand side would be (4(k + 1) - 3).
    Step 5: 1 + 5 + 9 + ---- + (4k - 3) + (4(k + 1) - 3) = k (2k - 1) + (4(k + 1) - 3)
    Step 6: = 2k2 - k + 4k + 1
    Step 7: = 2k2 + 3k + 1
    Step 8: = (k + 1)2 + k (k + 1)
    Step 9: = (k + 1) (2k + 1) [Factor.]
    Step 10: = (k + 1) (2(k + 1) - 1)
    Step 11: = Pk+1
    Step 12: So, the equation is true for n = k + 1.
    Step 13: Therefore, Pk is true for all positive integers, by mathematical induction.