1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Prove by induction

  1. Mar 8, 2009 #1
    I need to prove this by induction and I'm lost on how to even start, help please?

    Prove that for all positive integers k and n:

    ∑ j=1 through n, j(j+1)(j+2) . . . (j+k-1) = n(n+1)(n+2) . . . (n+k) / (k+1)
  2. jcsd
  3. Mar 9, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    Hi caseyd1981! :smile:

    Well, first it's a lot easier to read and quicker to write if you write it ∑ (j+k-1)!/(j-1)! = (n+k)!/(n-1)!(k+1)

    To prove by induction, assume it's true for n,

    then add (n+1+k-1)!/(n+1-1)! to both sides, and see what the right-hand side turns into :wink:
  4. Mar 9, 2009 #3
    Oh wow! I see now! Thank you so much for helping me start this one off. One more question, may I ask what is k in this statement? The index is j through n, so what exactly is k?
    Last edited: Mar 9, 2009
  5. Mar 10, 2009 #4


    User Avatar
    Science Advisor
    Homework Helper

    famous for fifteen seconds …

    Hi caseyd1981! :smile:
    o:) k is just an inoccent little constant o:) …​

    a passerby whom the producer persuaded to stand in for a scene because he needed an extra :wink:
  6. Mar 10, 2009 #5
    Alright, let's see. So what I need to prove is (n+1+k)!/(n+1-1)!(k+1)
    Which, simplified is: (n+1+k)!/n!(k+1)

    I add (n+1+k-1)!/(n+1-1)! to both sides and this is what my RHS becomes:

    (n+k)!/(n-1)!(k+1) + (n+1+k-1)!/(n+1-1)!

    (n+k)!/(n-1)!(k+1) + (n+k)!/n!

    Factor each denominator to find common denominator:
    (n-1)!(k+1) = (n-1)!(k+1)
    n! = n(n-1)!

    So the common denominator is n(n-1)!(k+1)

    I must multiply the left fraction's numerator by n and the right fraction's numerator by (k+1):
    n(n+k)!/n(n-1)!(k+1) + (n+k)!(k+1)/n(n-1)!(k+1)

    The denominator simplifies to n!(k+1)

    So now I have:
    n(n+k)! + (n+k)!(k+1)/n!(k+1)

    Hopefully I am on the right track here and have done everything correctly so far...
    Now I am stuck on adding the numerator. I am thinking I have to do some factoring? Not quite sure..

    ANd thank you SOOOO much for your help so far!! :)
  7. Mar 11, 2009 #6


    User Avatar
    Science Advisor
    Homework Helper

    hmm … this is rather long-winded …

    try starting it

    (n+k)!/(n-1)!(k+1) + (n+k)!/n!

    = (n+k)!/n!(k+1) (n + (k+1)) :wink:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook