Select Page
2 voices
• Author
Posts
• #21252
swastik pramanik
Participant

Prove by induction that the product n(n+1)(n+2)……..(n+r-1) of any consecutive r numbers is divisible by r!…

#21601
Tarit Goswami
Moderator

Assume $$k! | P(m,k)$$ for all $$m+k\le n$$. Now to show that $$k! | P(m,k)$$ for all $$m+k \le n+1$$

If $$m=1$$ we are done since $$P(1,k) = 1\cdot 2\cdots k = k!$$ and if $$k=1$$ then $$k! = 1!$$, clearly divides $$P(m,k)$$. So in the remainder

we may assume that $$m\ge 2$$ and $$k \ge 2$$. Also if $$m+k\le n$$ we are done vacuously, so consider only that $$m+k = n+1$$.

By the lemma we have $$P(m,k) = k\times P(m,k-1) + P(m-1,k)$$ so by the Induction hypothesis we have $$(k-1)! | P(m,k-1)$$

and thus also $$k! | k\times P(m,k-1)$$ and also by the Induction hypothesis $$k! | P(m-1,k)$$ and finally $$k! | P(m,k)$$ QED

• This reply was modified 7 months, 1 week ago by  Tarit Goswami.
topic tags

You must be logged in to reply to this topic.