Results 1 to 8 of 8
Like Tree8Thanks
  • 4 Post By Plato
  • 2 Post By emakarov
  • 1 Post By emakarov
  • 1 Post By Plato

Math Help - Induction problem

  1. #1
    Newbie
    Joined
    Apr 2013
    From
    Tokyo
    Posts
    8

    Induction problem

    Verify that

    1(1!)+2(2!)+...+n(n!) = (n+1)! - 1

    is true using induction

    For the nth case I plug in n = 1

    1(1!) = (1+1)! - 1
    1 = 2! - 1
    1 = 1 This is true

    For the n+1 case n = 1

    1(1!) + 2(2!)+...+n(n!)(n+1) = ((n+1)+1))! - 1

    n(n!)(n+1)((n+1)! - 1) = (n+2)! - 1

    1(1!)(1+1)((1+1)!-1) = (1+2)! - 1

    2 = 5 This is not true

    Therefore, this is not true on the n+1 case.

    Am I correct?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1

    Re: Induction problem

    Quote Originally Posted by RatchetTheLombax View Post
    Verify that

    1(1!)+2(2!)+...+n(n!) = (n+1)! - 1

    is true using induction

    For the nth case I plug in n = 1

    1(1!) = (1+1)! - 1
    1 = 2! - 1
    1 = 1 This is true

    If we use summation it is easier to see.

    The induction hypothesis is \sum\limits_{k = 1}^N {k\left[ {k!} \right]}  = \left( {N + 1} \right)!-1 is true.

    Look at \sum\limits_{k = 1}^{N+1} {k\left[ {k!} \right]}  = \sum\limits_{k = 1}^N {k\left[ {k!} \right]}+(N+1)[(N+1)!]  \\=\left[ {\left( {N + 1} \right)! - 1} \right] + (N + 1)\left[ {(N + 1)!} \right] = \left( {[N + 2]! - 1} \right)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Induction problem

    Quote Originally Posted by RatchetTheLombax View Post
    1(1!) + 2(2!)+...+n(n!)(n+1) = ((n+1)+1))! - 1

    n(n!)(n+1)((n+1)! - 1) = (n+2)! - 1
    The first line should probably be

    1(1!) + 2(2!)+...+(n+1)(n!)(n+1) = ((n+1)+1))! - 1

    Also, I don't understand how the second line is related to the first one.

    In general, proofs in the high school style consisting of a series of equalities ending with something like 1 = 1 are not used in higher mathematics. In a proof, it should be clear how subsequent claims follow from previous ones. Thus, real proofs may use long chains of equalities E1 = E2 = E3 = ..., possibly split over several lines and accompanied by short comments saying how each equality is obtained. Otherwise, a proof should be a sequence of claims joined by words or symbols such as "therefore", "thus" or "⇒", which show the relationship between the claims.
    Thanks from topsquark and RatchetTheLombax
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Apr 2013
    From
    Tokyo
    Posts
    8

    Re: Induction problem

    Quote Originally Posted by emakarov View Post
    The first line should probably be

    1(1!) + 2(2!)+...+(n+1)(n!)(n+1) = ((n+1)+1))! - 1

    Also, I don't understand how the second line is related to the first one.

    In general, proofs in the high school style consisting of a series of equalities ending with something like 1 = 1 are not used in higher mathematics. In a proof, it should be clear how subsequent claims follow from previous ones. Thus, real proofs may use long chains of equalities E1 = E2 = E3 = ..., possibly split over several lines and accompanied by short comments saying how each equality is obtained. Otherwise, a proof should be a sequence of claims joined by words or symbols such as "therefore", "thus" or "⇒", which show the relationship between the claims.
    What do you mean? You have to take the n and the n+1 case and prove they are equal.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Induction problem

    Quote Originally Posted by RatchetTheLombax View Post
    What do you mean? You have to take the n and the n+1 case and prove they are equal.
    Now I am not sure what you mean by n-case and (n+1)-case. A proof by induction starts with identifying a property of natural numbers, often denoted by P(n). For each n, P(n) is either true or false (in particular, P(n) is not a number). This property can be an equality, as in the current problem, but it can have other forms: e.g., e1(n) divides e2(n) for some expressions e1 and e2, e(n) is a triangular number for some e, etc. The problem is to prove that P(n) holds for all natural n ≥ n0. The base case consists of proving P(n0). The induction step consists of proving that P(n) implies P(n+1) for all n ≥ n0.

    In this problem, P(n) is 1(1!) + 2(2!) + ... + n(n!) = (n+1)! - 1; therefore, P(n+1) is 1(1!) + 2(2!) + ... + (n+1)(n+1)! = (n+2)! - 1. I assumed the line

    1(1!) + 2(2!)+...+n(n!)(n+1) = ((n+1)+1))! - 1

    in post #1 supposed to be P(n+1). That's why I said n(n!)(n+1) should be replaced by (n+1)(n!)(n+1) = (n+1)(n+1)!.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Apr 2013
    From
    Tokyo
    Posts
    8

    Re: Induction problem

    Quote Originally Posted by emakarov View Post
    Now I am not sure what you mean by n-case and (n+1)-case. A proof by induction starts with identifying a property of natural numbers, often denoted by P(n). For each n, P(n) is either true or false (in particular, P(n) is not a number). This property can be an equality, as in the current problem, but it can have other forms: e.g., e1(n) divides e2(n) for some expressions e1 and e2, e(n) is a triangular number for some e, etc. The problem is to prove that P(n) holds for all natural n ≥ n0. The base case consists of proving P(n0). The induction step consists of proving that P(n) implies P(n+1) for all n ≥ n0.

    In this problem, P(n) is 1(1!) + 2(2!) + ... + n(n!) = (n+1)! - 1; therefore, P(n+1) is 1(1!) + 2(2!) + ... + (n+1)(n+1)! = (n+2)! - 1. I assumed the line

    1(1!) + 2(2!)+...+n(n!)(n+1) = ((n+1)+1))! - 1

    in post #1 supposed to be P(n+1). That's why I said n(n!)(n+1) should be replaced by (n+1)(n!)(n+1) = (n+1)(n+1)!.
    You are probably right. Induction doesn't make any sense at all. I understand what it is but that is the extent of it.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1

    Re: Induction problem

    [QUOTE=RatchetTheLombax;785496]You are probably right. Induction doesn't make any sense at all. I
    understand what it is but that is the extent of it.[/QUOTE

    Why do you say that?

    Here is a real-world example.
    Think of a garden path made up of stepping stones.
    Now suppose I show you that there is absolutely a way that you can get onto the first stone in the path.
    Then I show you that if you are on any stone then you can absolutely 'move' to the next stone.
    Does that not mean that "you can start at the first stone and move through the entire garden path?
    You can get on at S_1, but then you have a grantee you can go to S_2 then to S_3, etc.

    That is what induction is all about.
    We can step on all positive integers for a statement.
    Last edited by Plato; May 2nd 2013 at 04:50 PM.
    Thanks from emakarov
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Jul 2012
    From
    INDIA
    Posts
    834
    Thanks
    209

    Re: Induction problem

    Induction problem-10-may-13-math-induction.png
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Induction Problem
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 26th 2010, 06:00 AM
  2. induction problem
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: May 17th 2010, 01:02 AM
  3. induction problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 22nd 2010, 08:28 AM
  4. induction problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 26th 2009, 08:34 AM
  5. INDUCTION PROBLEM
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 26th 2008, 09:16 AM

Search Tags


/mathhelpforum @mathhelpforum