Results 1 to 6 of 6

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

    $\displaystyle n!<n^n$

    by $\displaystyle n+1$ to get:

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

    So:

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

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

    $\displaystyle (n+1)^{n+1}=n^{n+1}+(n+1)n^n+R $

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

    So:

    $\displaystyle (n+1)^{n+1}=n^{n+1}+n^n+n^{n+1}+R $

    Hence:

    $\displaystyle (n+1)^{n+1}>n^{n+1}+n^n $

    and so going back to $\displaystyle (1)$ we have:

    $\displaystyle (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:

    $\displaystyle n!<n^n$

    by $\displaystyle n+1$ to get:

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

    So:

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

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

    $\displaystyle (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
    5
    Quote Originally Posted by sjenkins View Post
    Quote Originally Posted by CaptainBlack View Post
    Multiply both sides of:

    $\displaystyle n!<n^n$

    by $\displaystyle n+1$ to get:

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

    So:

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

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

    $\displaystyle (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:

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

    Now by the rules of indices:

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

    so:

    $\displaystyle (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
    5
    Quote Originally Posted by sjenkins View Post
    Quote Originally Posted by CaptainBlack View Post
    Multiply both sides of:

    $\displaystyle n!<n^n$

    by $\displaystyle n+1$ to get:

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

    So:

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

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

    $\displaystyle (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:

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

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

    $\displaystyle
    (n+1)^{n+1}=n^{k+1}+(n+1)n^k + \text{ and other terms all positive}
    $

    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: Apr 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Apr 19th 2010, 05:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 09:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 7th 2008, 04:10 PM

Search Tags


/mathhelpforum @mathhelpforum