Results 1 to 6 of 6

Math Help - More induction help

  1. #1
    Member
    Joined
    May 2008
    Posts
    109

    More induction help

    Can someone give me a hint as to where to start while attempting this problem?

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

  2. #2
    Member
    Joined
    May 2008
    Posts
    109
    This is what I have so far...

    Basis step: P(2) states that 2! is less than 2^2. This is true since 2! = 2 and 2^2=4 and 2<4.

    Inductive step: Assume n is greater than 1. Assume P(n) is true: that is
    n! < n^n


    This is where I am stuck!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by sjenkins View Post
    This is what I have so far...

    Basis step: P(2) states that 2! is less than 2^2. This is true since 2! = 2 and 2^2=4 and 2<4.

    Inductive step: Assume n is greater than 1. Assume P(n) is true: that is
    n! < n^n


    This is where I am stuck!
    Multiply both sides of:

    n!<n^n

    by n+1 to get:

    (n+1) \times n!=(n+1)! < (n+1) \times n^n

    So:

    (n+1)!<n^{n+1}+n^n \ \ \ \ \ \ \ ...(1)

    Now taking the first two terms of the binomial expansion of (n+1)^{n+1} we get:

    (n+1)^{n+1}=n^{n+1}+(n+1)n^n+R

    where R>0 is the remainder (which is greater than zero because all of the terms left out of this are also positive).

    So:

    (n+1)^{n+1}=n^{n+1}+n^n+n^{n+1}+R

    Hence:

    (n+1)^{n+1}>n^{n+1}+n^n

    and so going back to (1) we have:

    (n+1)!<n^{n+1}+n^n<(n+1)^{n+1}

    which completes the proof of the induction step.

    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2008
    Posts
    109
    [quote=CaptainBlack;164709]Multiply both sides of:

    n!<n^n

    by n+1 to get:

    (n+1) \times n!=(n+1)! < (n+1) \times n^n

    So:

    (n+1)!<n^{n+1}+n^n \ \ \ \ \ \ \ ...(1)

    Now taking the first two terms of the binomial expansion of (n+1)^{n+1} we get:

    (n+1)^{n+1}=n^{n+1}+(n+1)n^n+R


    Can you please explain how to factor these, I don't understand how, for example (n+1)Xn^n becomes n^n+1+n^n. I also am not understanding the part where it says taking the first two terms of the binomail expansion... where did that come from?

    I'm sorry to sound so crazy, I just am not grasping this quite yet!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by sjenkins View Post
    Quote Originally Posted by CaptainBlack View Post
    Multiply both sides of:

    n!<n^n

    by n+1 to get:

    (n+1) \times n!=(n+1)! < (n+1) \times n^n

    So:

    (n+1)!<n^{n+1}+n^n \ \ \ \ \ \ \ ...(1)

    Now taking the first two terms of the binomial expansion of (n+1)^{n+1} we get:

    (n+1)^{n+1}=n^{n+1}+(n+1)n^n+R

    Can you please explain how to factor these, I don't understand how, for example (n+1)Xn^n becomes n^n+1+n^n. I also am not understanding the part where it says taking the first two terms of the binomail expansion... where did that come from?

    I'm sorry to sound so crazy, I just am not grasping this quite yet!
    Multiply out the bracket:

    (n+1)  n^n= n \times n^n +n^n

    Now by the rules of indices:

    n \times n^n=n^{n+1},

    so:

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

    RonL
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by sjenkins View Post
    Quote Originally Posted by CaptainBlack View Post
    Multiply both sides of:

    n!<n^n

    by n+1 to get:

    (n+1) \times n!=(n+1)! < (n+1) \times n^n

    So:

    (n+1)!<n^{n+1}+n^n \ \ \ \ \ \ \ ...(1)

    Now taking the first two terms of the binomial expansion of (n+1)^{n+1} we get:

    (n+1)^{n+1}=n^{n+1}+(n+1)n^n+R

    Can you please explain how to factor these, I don't understand how, for example (n+1)Xn^n becomes n^n+1+n^n. I also am not understanding the part where it says taking the first two terms of the binomail expansion... where did that come from?

    I'm sorry to sound so crazy, I just am not grasping this quite yet!
    You should know the binomial theorem:

    (a+b)^k=a^k + k a^{k-1}b + .. +<br />
\left( {\begin{array}{*{20}c}<br />
k \\<br />
r \\<br />
\end{array}} \right)a^{k-r}b^r + .. +kab^{k-1}+b^k<br />

    So apply this to (n+1)^{n+1} with a=n, b=1 and k=n+1 to get:

     <br />
(n+1)^{n+1}=n^{k+1}+(n+1)n^k + \text{ and other terms all positive}<br />

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 19th 2010, 05:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 7th 2008, 04:10 PM

Search Tags


/mathhelpforum @mathhelpforum