Results 1 to 5 of 5
Like Tree1Thanks
  • 1 Post By romsek

Math Help - Proving an expression with induction

  1. #1
    Newbie
    Joined
    Nov 2013
    From
    England
    Posts
    5

    Proving an expression with induction

    I have an assignment which I am quite stuck on. The question is the following:
    function f: N to N is defined recursivly:


    f(k+1)=(k+1)*f(k) for each k in N. f(0)=1.


    Now I have to prove by induction:


    1* f (1) + 2 * f (2) + 3* f (3) +....+n * f (n) = f (n +1) -1


    I have made two steps:
    1. proved that the equation is true for n=1.
    2. I assume that the equation is true for n.


    Now I have to prove the equation for n+1.


    Now the equation is:


    1* f (1) + 2 * f (2) + 3* f (3) +....+n * f (n) + (n+1)*f(n+1) = f (n +2) -1


    I have used the induction assumption (number 2 in my steps) to place:


    f (n +1)-1
    insted of:


    1* f (1) + 2 * f (2) + 3* f (3) +....+n * f (n)


    So now I got:


    f(n+1)-1 + (n+1)*f(n+1)=f(n+2)-1


    With a common factor of f(n+1) I got:


    f(n+1)(n+2)=f(n+2)


    Now this is the last step I made.


    My question:
    Can I, from the first definition, say the this final equation is true?


    I mean, this is the factorial definition.
    The assignment is that, so that's what I have to prove even if there's not much sense :-)


    I can't PROVE my final step. Please help.
    Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,225
    Thanks
    851

    Re: Proving an expression with induction

    Quote Originally Posted by nerazzurri10 View Post
    I have an assignment which I am quite stuck on. The question is the following:
    function f: N to N is defined recursivly:


    f(k+1)=(k+1)*f(k) for each k in N. f(0)=1.


    Now I have to prove by induction:


    1* f (1) + 2 * f (2) + 3* f (3) +....+n * f (n) = f (n +1) -1


    I have made two steps:
    1. proved that the equation is true for n=1.
    2. I assume that the equation is true for n.


    Now I have to prove the equation for n+1.


    Now the equation is:


    1* f (1) + 2 * f (2) + 3* f (3) +....+n * f (n) + (n+1)*f(n+1) = f (n +2) -1


    I have used the induction assumption (number 2 in my steps) to place:


    f (n +1)-1
    insted of:


    1* f (1) + 2 * f (2) + 3* f (3) +....+n * f (n)


    So now I got:


    f(n+1)-1 + (n+1)*f(n+1)=f(n+2)-1
    This is where you've made your mistake. Don't set the left hand side equal to f(n+2)-1. You want to show that it is equal.

    so you would say f(n+1)-1 + (n+1)f(n+1) = (n+2)f(n+1) - 1 = f(n+2) - 1, the last bit by the definition of f(n+2)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2013
    From
    England
    Posts
    5

    Re: Proving an expression with induction

    So you're saying that I should go on with:
    f(n+1)-1 + (n+1)f(n+1) = (n+2)f(n+1) - 1

    And prove that equation?

    Thank you!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,225
    Thanks
    851

    Re: Proving an expression with induction

    Quote Originally Posted by nerazzurri10 View Post
    So you're saying that I should go on with:
    f(n+1)-1 + (n+1)f(n+1) = (n+2)f(n+1) - 1

    And prove that equation?

    Thank you!
    yes, just note that (n+2)f(n+1) = f(n+2) by the definition of f
    Thanks from nerazzurri10
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2013
    From
    England
    Posts
    5

    Re: Proving an expression with induction

    Thank you. Followed your advice.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. closed-form expression and induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 14th 2013, 12:04 PM
  2. Proving by Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 4th 2012, 05:30 PM
  3. Proving by induction
    Posted in the Algebra Forum
    Replies: 7
    Last Post: September 23rd 2012, 10:16 PM
  4. Proving expression with sines.
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: February 26th 2011, 01:00 PM
  5. Help proving this expression is equal..
    Posted in the Calculus Forum
    Replies: 4
    Last Post: November 27th 2008, 03:33 AM

Search Tags


/mathhelpforum @mathhelpforum