Results 1 to 4 of 4

Math Help - Mathematical induction

  1. #1
    Member
    Joined
    May 2008
    Posts
    109

    Unhappy Mathematical induction

    Can anyone explain mathematical induction to me? I have a whole chapter worth of problems and do not even begin to understand.

    Here are a couple of examples:
    Show that 1^3+2^3+...+n^3=[n(n+1)/2]^2 whenever n is a positive integer.

    Use mathematical induction to prove that n!<n^n whenever n is a postive integer greater than 1.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Sorry for the "innovation", but I copied it from one of my other posts..

    Ok, there are three main steps in an induction proof

    Preliminary : state the induction property P_n


    This is mostly for yourself, to clear out the view.

    1st step : the basis.
    You have to check that this is true for the very first term.

    2nd step : the inductive step.
    Induction hypothesis : assume that the property is true for a rank n.

    Then, prove that if this is verified for a rank n, it will be for the following rank, n+1.


    In most of the induction exercises, this proof will require you to go back to the recursive definition of P_n
    Also see here : Mathematical induction - Wikipedia, the free encyclopedia

    -----------------------------
    Here, P_n \ : \ 1^3+2^3+...+n^3=\left[\frac{n(n+1)}{2}\right]^2 ~,~ \text{whenever n is a positive integer, that is to say } n \ge 1.



    Basis : Prove that P_1 is true << this is easy here;

    Inductive hypothesis : 1^3+2^3+...+n^3=\left[\frac{n(n+1)}{2}\right]^2


    Prove that P_{n+1} is true : 1^3+2^3+...+n^3+(n+1)^3=\left[\frac{(n{\color{red}+1})(n+{\color{red}2})}{2}\rig  ht]^2.

    proof :
    1^3+2^3+...+n^3+(n+1)^3=\left[\frac{n(n+1)}{2}\right]^2+(n+1)^3, according to the inductive hypothesis.

    =\frac{[n(n+1)]^2}{4}+(n+1)^3

    =\frac{n^2(n+1)^2+4(n+1)^3}{4}

    Factor by (n+1)^2:

    =\frac{(n+1)^2[{\color{blue}n^2+4(n+1)}]}{4} (1)

    -----------------------------
    On your draft paper, note that you have to prove that this is equal to \frac{[(n+1)(n+2)]^2}{4}=\frac{(n+1)^2{\color{blue}(n+2)^2}}{4}, that is to say prove that n^2+4(n+1)=(n+2)^2

    -----------------------------

    So factor (1) correctly, in order to get what you want...
    In fact, you should always be able to keep in mind what formula you want to prove (the P_{n+1} thing).




    Is it clear enough ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Use mathematical induction to prove that n!<n^n whenever n is a postive integer greater than 1.
    P_n \ : \ n! < n^n ~,~ n \ge 2.

    P_2 \ : \ 2!<2^2 ???

    2!=2
    2=4.

    So P_2 is true.

    ----------------
    Assume that n!<n^n (inductive hypothesis).


    Prove that (n+1)!<(n+1)^{n+1}.

    (n+1)^{n+1}=(n+1)^n \cdot (n+1)

    But n+1>n \quad \implies \quad (n+1)^n>n^n.


    So we have (n+1)^{n+1}>n^n \cdot (n+1).

    The inductive hypothesis lets us know that n^n>n!.


    Therefore (n+1)^{n+1}>n^n \cdot (n+1)>n! \cdot (n+1)=(n+1)! \quad \square


    Do you understand it ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2008
    Posts
    109
    I wish I did understand. I will look at your answers and really try to grasp this concept. I have only 18 problems left and I will be finished with this course (and thank goodness because I haven't understood a bit of it). Thank you for your help and I will look at it carefully to see if I can understand what you have written.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 31st 2010, 03:31 PM
  2. Mathematical induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 30th 2010, 05:54 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. mathematical induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 13th 2009, 05:29 PM
  5. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 18th 2009, 08:35 AM

Search Tags


/mathhelpforum @mathhelpforum