Prove by induction

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)
 

tiny-tim

Science Advisor
Homework Helper
25,799
242
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)
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:
 
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:

tiny-tim

Science Advisor
Homework Helper
25,799
242
famous for fifteen seconds …

Hi caseyd1981! :smile:
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)
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?
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:
 
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!! :)
 

tiny-tim

Science Advisor
Homework Helper
25,799
242
(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)
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:
 

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top