Scribd Logo
Upload

Welcome to Scribd!

  • 7 views

    A1. Mathematical Induction

    Uploaded by

    Liu jingyan
    Mathematical induction is a method of proof used to prove that a formula holds for all positive integers n. The proof involves two steps: 1) proving the base case, which is showing the formula holds for n=1, and 2) proving the inductive step, which assumes the formula holds for an integer k and uses this to prove it holds for k+1. An example is given of using induction to prove the formula for the sum of the first n positive integers. A counterexample is also provided to show a claim that n5 ≥ n! does not always hold.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    A1. Mathematical Induction

    Uploaded by

    Liu jingyan
    7 views6 pages
    Mathematical induction is a method of proof used to prove that a formula holds for all positive integers n. The proof involves two steps: 1) proving the base case, which is showing the formula holds for n=1, and 2) proving the inductive step, which assumes the formula holds for an integer k and uses this to prove it holds for k+1. An example is given of using induction to prove the formula for the sum of the first n positive integers. A counterexample is also provided to show a claim that n5 ≥ n! does not always hold.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Mathematical induction is a method of proof used to prove that a formula holds for all positive integers n. The proof involves two steps: 1) proving the base case, which is showing the formula holds for n=1, and 2) proving the inductive step, which assumes the formula holds for an integer k and uses this to prove it holds for k+1. An example is given of using induction to prove the formula for the sum of the first n positive integers. A counterexample is also provided to show a claim that n5 ≥ n! does not always hold.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    7 views6 pages

    A1. Mathematical Induction

    Uploaded by

    Liu jingyan
    Mathematical induction is a method of proof used to prove that a formula holds for all positive integers n. The proof involves two steps: 1) proving the base case, which is showing the formula holds for n=1, and 2) proving the inductive step, which assumes the formula holds for an integer k and uses this to prove it holds for k+1. An example is given of using induction to prove the formula for the sum of the first n positive integers. A counterexample is also provided to show a claim that n5 ≥ n! does not always hold.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 6

    MA2002: Calculus

    Mathematical Induction
    Purpose

    For proving that a formula holds for every positive integer n. For example
    (i)
    n(n + 1)
    1 + 2 + 3 + ··· + n − 1 + n = ,
    2

    (ii)
    1 1 1 1 1
    + + + 3 + ··· + n = 1 − n,
    2 22 2 2 2

    (iii)
    1 − r n+1
    1 + r + r2 + r3 + · · · + rn = , r ̸= 1, etc.
    1−r
    Method
    The steps in proving a formula by induction are the following
    1. (Base case) Check that the formula holds for n = 1.

    2. (Inductive step) Prove that if the formula holds for an positive integer n = k, then it also
    holds for the next integer n = k + 1.
    Example
    Prove that
    n(n + 1)
    1 + 2 + 3 + ··· + n − 1 + n = .
    2

    1. (Base case) n = 1

    2. (Inductive step) Suppose it is true that

    k(k + 1)
    1 + 2 + 3 + ··· + k − 1 + k = .
    2
    Then for n = k + 1,
    Counterexample
    Claim
    n5 ≥ n!
    for all positive integer n.

    n=1 15 = 1 ≥ 1 = 1!
    n=2 25 = 32 ≥ 2 = 2!
    n=3 35 = 243 ≥ 6 = 3!
    n=4 45 = 1024 ≥ 24 = 4!

    However,
    105 = 100000 < 3628800 = 10!.
    Other Starting Integers

    Show that
    n! > 3n
    if n is large enough.
    1. (Base case) n = 7
    7! = 5040 > 2187 = 37 .

    2. (Inductive step) Suppose k! > 3k for some k > 7. Then

    You might also like