Results 1 to 9 of 9

Thread: Mathematical induction

  1. #1
    Newbie charlynmaybituin's Avatar
    Joined
    Aug 2015
    From
    US
    Posts
    4

    Mathematical induction

    Plese help me with this:

    Use mathematical induction to prove this (n+1)^n < (n)^n+1 for all n> or =3.

    Is anyone has an idea? I find it so hard.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    12,841
    Thanks
    1931

    Re: Mathematical induction

    Have you tried anything so far? What is the base step?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie charlynmaybituin's Avatar
    Joined
    Aug 2015
    From
    US
    Posts
    4

    Re: Mathematical induction

    This is the first step. Suppose n=k. Where k is equal or greatee than 3.

    (K+1)^k < (k)^k+1
    [K(1+1/k)]^k < k^k *k
    K^k *(1+1/k)^k <k^k *k
    (1+1/k)^k < k

    Trivial case: if k=3
    (1+1/3)^3 < 3
    2.37< 3

    Second step: suppose n= k is true. Then n= k+1 must be also true.
    I have a problem with this step. I cant prove it. 😥😥😥😥
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    1,061
    Thanks
    410

    Re: Mathematical induction

    Method by trying to "work backwards":

    You could do the inductive step in one line if it were true that: \frac{(n+2)^{n+1}}{(n+1)^n} < \frac{(n+1)^{n+2}}{n^{n+1}} (for n \ge 3).

    Do you see why? Since everything in sight is positive, you'd have, for n \ge 3, that:

    0 < (n+1)^n < n^{n+1} (your inductive assumption) and 0 < \frac{(n+2)^{n+1}}{(n+1)^n} < \frac{(n+1)^{n+2}}{n^{n+1}} (this wonderful thing that gets the job done if it happens to be true)

    and therefore 0 < \left( (n+1)^n \right) \ \left( \frac{(n+2)^{n+1}}{(n+1)^n} \right) < \left( n^{n+1} \right) \ \left( \frac{(n+1)^{n+2}}{n^{n+1}} \right),

    which would prove that 0 < (n+2)^{n+1} < (n+1)^{n+2}.

    And that would prove the induction.

    Do you see why I called that working backwards? I chose to consider \frac{(n+2)^{n+1}}{(n+1)^n} < \frac{(n+1)^{n+2}}{n^{n+1}} because, if it were true, it would be exactly what would be needed to get the job done.

    It turns out that \frac{(n+2)^{n+1}}{(n+1)^n} < \frac{(n+1)^{n+2}}{n^{n+1}} is true (actually for all n \ge 1), and you can prove that directly with some algebra. Can you see how?
    Last edited by johnsomeone; Aug 17th 2015 at 05:53 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie charlynmaybituin's Avatar
    Joined
    Aug 2015
    From
    US
    Posts
    4

    Re: Mathematical induction

    Im sosory. I just dont get it on how you started the process. 😥
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,815
    Thanks
    588

    Re: Mathematical induction

    An alternative approach is to examine the binomial expansion$$(n+1)^{n+2}=\sum_{k=0}^{n+2}{n +2\choose k}n^k$$
    We can use the inductive assumption on each term and the identity $${m+1 \choose i} = {m \choose i-1} + {m \choose i}$$
    This should lead to something similar (but greater than) the binomial expansion of $$(n+2)^{n+1} = \big((n+1)+1\big)^{n+1}=\sum_{j=0}^{n+1} {n+1 \choose j}(n+1)^j$$
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,671
    Thanks
    313

    Re: Mathematical induction

    Hard to tell if you REALLY can't...or are too lazy

    Go read up a bit:
    https://www.google.ca/?gws_rd=ssl#q=...ical+induction
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    1,116
    Thanks
    465

    Re: Mathematical induction

    Johnsomething has given you an excellent answer; his technique of working backwards from a desired conclusion is very typical of how proofs are discovered. For example, to prove the diagonals of a rectangle are equal, you work backwards and say to yourself: if these two triangles are congruent, I'm done. You then proceed to show the triangles are congruent. In the following direct proof as indicated by John, the inequality of the 4th part of the lemma is what makes the inductive step possible. He has tried to indicate this inequality is not a "rabbit out of the hat", but is "clearly" what is needed for the proof.
    BTW, to prove a sequence of statements P(n) true by induction, you do not need to introduce a new variable k. That is, the inductive step can be: assume P(n) true. Thus ... P(n+1) is true. This is exactly the same as: assume P(k) is true, and then deduce that P(k+1) is true.

    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie charlynmaybituin's Avatar
    Joined
    Aug 2015
    From
    US
    Posts
    4

    Re: Mathematical induction

    Thanks all!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. mathematical induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 7th 2010, 08:05 PM
  2. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  3. Some help on mathematical induction?
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Nov 30th 2009, 02:34 AM
  4. Mathematical Induction
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: May 14th 2008, 06:39 AM
  5. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: May 12th 2008, 01:25 PM

Search Tags


/mathhelpforum @mathhelpforum