1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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


    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:
    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:

    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


    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


    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook