inductive reasoning


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.

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

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.

Related Terms for Induction

  • Deductive Reasoning
  • Inductive Reasoning
  • Mathematical Induction