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

    tiny-tim

    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

    tiny-tim

    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)!

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

    Factor each denominator to find common denominator:
    (n-1)!(k+1) = (n-1)!(k+1)
    And
    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

    tiny-tim

    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