Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mathematical induction

  1. Aug 19, 2012 #1
    what is mathematical induction? explain with an example.
     
  2. jcsd
  3. Aug 19, 2012 #2

    PhysicoRaj

    User Avatar
    Gold Member

    Mathematical Induction is a concept used to prove a given statement to be true for all positive integers. It is generally described with an example of effect of sequential falling of plates arranged parallel, up to a long distance. If one falls over the next, the whole sequence undergoes the same effect.
    Theoretically it is done in three main steps:
    1) Proving the statement to be true for the value 1
    and hence showing the either sides of equation to be equal.
    2) Proving for (k+1) value and implying on k-->(k+1)
    3) Showing that the implication and the true value concludes the statement to be true for all n belonging to natural numbers.
    An example:
    Mathematical induction can be used to prove that the following statement, which we will call P(n), holds for all natural numbers n.
    1+2+3+..........+n = n(n+1)/2
    P(n) gives a formula for the sum of the natural numbers less than or equal to number n. The proof that P(n) is true for each natural number n proceeds as follows.
    Show that the statement holds for n = 1.
    P(1) amounts to the statement:
    1=1.(1+1)/2
    In the left-hand side of the equation, the only term is 1, and so the left-hand side is simply equal to 1.
    In the right-hand side of the equation, 1·(1 + 1)/2 = 1.
    The two sides are equal, so the statement is true for n = 1. Thus it has been shown that P(1) holds.
    Show that if P(k) holds, then also P(k + 1) holds. This can be done as follows.

    Assume P(k) holds (for some unspecified value of k). It must then be shown that P(k + 1) holds, that is:
    1+2+...........+k+(k+1) = (k+1)[(k+1)+1]/2

    Using the induction hypothesis that P(k) holds, the left-hand side can be rewritten to:
    [k(k+1)/]+(k+1)

    Algebraically it is equal to (k+1)[(k+1)+1]/2
    thereby showing that indeed P(k + 1) holds.

    Since both the basis and the inductive step have been proved, it has now been proved by mathematical induction that P(n) holds for all natural n.
     
    Last edited: Aug 19, 2012
  4. Aug 19, 2012 #3
    Why do we have to turn k into n? Why can't we just use k the whole time since that is what we use in the original question?
     
  5. Aug 19, 2012 #4

    Bacle2

    User Avatar
    Science Advisor

    Well, it is a purely technical issue: the property holds for the natural number 1

    (tho this is not always necessary), and we denote that it is satisfied by the natural

    number n=k, and we want this last to imply that the property holds also for the

    proposition P(k+1), which is indexed by the natural number n=k+1.

    Look up too, the well-ordering principle , which is equivalent to induction

    --we use the fact that in standard induction, the propositions are indexed by the

    natural numbers with their standard ordering. You may also want to look up

    transfinite induction , which generalizes standard induction to well-ordered sets
     
  6. Aug 21, 2012 #5

    PhysicoRaj

    User Avatar
    Gold Member

    P(n) is the general form. The proof is given to show both for values of 1 (sometimes it is also proved for 0) and any other natural number k and k+1, the statement holds true, which for the sake of convenience you can do with n+1 and n.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Mathematical induction
  1. Mathematical induction (Replies: 9)

  2. Mathematical Induction (Replies: 1)

  3. Mathematical induction (Replies: 5)

  4. Mathematical Induction (Replies: 9)

  5. Mathematical induction (Replies: 2)

Loading...