# Prove by induction

1. Mar 8, 2009

### caseyd1981

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. Mar 9, 2009

### tiny-tim

Hi caseyd1981!

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

3. Mar 9, 2009

### caseyd1981

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
4. Mar 10, 2009

### tiny-tim

famous for fifteen seconds …

Hi caseyd1981!
k is just an inoccent little constant …​

a passerby whom the producer persuaded to stand in for a scene because he needed an extra

5. Mar 10, 2009

### caseyd1981

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

6. Mar 11, 2009

### tiny-tim

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